I still think that GhostScript cannot solve this problem. What you need is something that analyzes a PDF, similar to OCR software. pdftotext basically should do exactly this. And if it fails in some cases, you should go to
http://poppler.freedesktop.org/, find the people who maintain the pdftotext module, and submit some cases where it mixes up lines.
But note that I'm not a pdf expert, so don't take my advice as a gospel...
Luc