@BaCaRdi,
I'm no physicist or "expert" in paradoxes, but Nietzsche's own rejection of atomistic cause and effect vis-a-vis the "will" seems to preclude the possibility of a universe in which there are only a finite number of possibilities. I refer most specifically to BG&E section 21 and his attack on the concept of the "unfreedom of the will", that is, will and willing as the result of the great billiard-ball course of atomistic cause and effect.
Perhaps I have misunderstood him, but I believe N's position to have been that the core energy of existence (or at least the emergent property of such, that is, life) - his "will to power" - was
not constrained by any mechanical possibilities. That is, though there are certainly a finite number of possible physical outcomes of any particular act of willing, there are not a finite number of things that can be willed. This is, by my understanding, the whole concept of "free" will in his naturalistic system.
Willing (which is life) is not a predictable sequence of physical events, one following from the next.
If the possibilities for willing are infinite, then it follows that even in an infinity of time, the same state could not repeat itself. And since Nietzsche clearly rejects Cartesian dualism in favor of a shockingly modern "emergent phenomenon" theory of life (BG&E 36) with "will" as its only source of causality, it follows that the possible arrangements of reality are infinite - reality defined as a single entity - everything is "will to power".
It seems to me that Nietzsche's attack on the concept of objective truth flows from this source. What is "truth" in a universe of infinite possibilities? In order for truth, in the Platonic sense, to exist, the infinite must be constrained into the finite. Nietzsche wholeheartedly rejected that.
I think his concept of eternal recurrence was really more a challenge than a statement on his opinion of reality. Can you live with the idea of it: a profound test of just how well one has accepted his concept of existence...even if eternal recurrence, itself, is not "true". Eternal recurrence is only possible in a "billiard ball" universe in which "life" or "will" or whatever you want to call it has no causal force outside of deterministic atomism - that is, life cannot "create" force on its own, and our existence is just a physical wave of atoms or energy or "wills to power" or whatnot crashing into each other from the big bang to the end of time and over and over and over. I think Nietzsche considered this track of thinking among the most profound denials of life.
As for my own opinion, I do not believe in eternal recurrence.