My twin 10^29^29 ly away... if he picks up an astronomy atlas, will he find the exact same objects listed with the exact same coordinates digit for digit?

Probably not. Copies of bokov are pretty rare in the universe (one every 10^(10^29) meters), but copies of bokov together with a correct copy of the whole observable universe have got to be vastly rarer. Only one out of every (insanely huge number) would see the same night sky you do.

In general, you're not guaranteed to see any particular pattern more than once, or for the pattern of repetition to be particularly neat. The pigeonhole principle says that with an infinite number of pigeons placed into a finite number of slots, at least one of the slots needs to contain more than one pigeon (in fact, one or more of them needs to contain an infinite number of pigeons). But it doesn't say that all of the slots need to be filled more than once.

Is cyclicity a necessary consequence of filling an infinite space with things that can only have a finite number of configurations?

Eventually you have to return to a point you have been before, but the cycle need not encompass all the possibilities. For example an infinite string of the numbers 0-5 could go as follows 1, 2, 3, 4, 5, 0, 5, 0, 5, 0, ...

If so, does that mean if I zoom in on a Mandelbrot set far enough I will see an exact replica of the image I started with

Not necessarily, because the number of "possible" images (a continuous infinity, equivalent to R^R) is not smaller than the number of possible "zoom" positions (a smaller continuous infinity equivalent to R).

if I run a cellular automaton long enough I will get a regular pattern?

You're not guaranteed to see any particular pattern, as I said, and in fact conway's game of life has "garden of eden" configurations, which can't be obtained by running the cellular automaton from any possible starting position. So you don't even go through all the "theoretically possible" states before cycling.

But, in the case Eliezer mentioned, I think it's fairly reasonable to assume that there is in fact a copy of you somewhere out there, assuming the world is infinite, because of things like quantum "randomness" and thermal noise that give each section of space an independent chance of spontaneously manifesting pretty much any configuration of matter, and those chances add up to "certainty" after an infinite number of chances.