Fragmented recovered image using a Phase Retrieval Algorithm named Error-Reduction
I think the effect you're seeing can be explained in terms of the shift theorem of Fourier transforms and the periodicity of the discrete Fourier transform.  

It looks like the recovered object has been shifted upwards, and because the DFT is periodic, the top part of the object that's left the field of view has wrapped around to re-appear at the bottom of the field.
The reason the object is shifted is hard to see without knowing more about how your implementation of phase retrieval.  I can say that, due to the shift theorem, we know a shift in the object domain causes a linear phase in the Fourier domain, but does not affect the Fourier modulus.  So, the Fourier modulus alone can't help you find the correct shift.
I suspect you're leaving out some key information when you say "The only information given is the Fourier Modulus", because if that were strictly true you wouldn't be able to do phase retrieval at all.  As discussed in the paper, you need to have some other piece of information, typically the modulus of the object or the object support (the object support is a closed boundary that you know contains the object).  If you know the modulus of the object or at least its support, then reinforcing that constraint on every iteration of the error-reduction algorithm would prevent the object estimate from shifting.

As to your third question, I would point out that error-reduction is only the simplest algorithm discussed in the paper.  Gradient searches or the input-output methods described in the later sections are usually faster and/or more reliable.  In more recent years, successful methods that leverage nonlinear optimization algorithms such as BFGS have also become common. If you're interested, you might check out Prof. Fienup's list of publications.