Just writing up this bug so that anyone else who encounters it can find out what's going on with less head-scratching.
It seems that InDesign's data merge feature gets confused when there are anchored objects in a text frame that's anchored inside another text frame, which can result in:
(sadly I can't provide a file for confidentiality reasons - but the problem point had multi-line data merge entries, a text frame that was anchored in another text frame of equal width, and anchored images and text frames in this anchored text frame)
There were certain entires where, if I navigate to them in the preview using the 'next' and 'previous' keys, there was 4mm less space between the nested text frame and the previous line than if I navigate to it by entering the number. Exporting as a PDF through data merge used the variant with more space.
Re-working the area in question so that the nested text frame wasn't needed seems to have removed the problem (but loses the ability to vertically align these elements in a fixed size frame that is in the text flow).
You didn't say what version of ID, or whter a single or multiple record per page merge, but the Preview is known to be buggy for multiple records since CS5 and might be for single records as well.
I have an annual directory that is built by data merge with one section in each listing as an anchored frame, and I've never had a problem, but it's not as complex as your description, nor do I ever merge to PDF (though I've heard here from several users that it's more reliable).
One thing you might want to try is merging without the preview step, but do it from a "fresh" file by copying and pasting your placeholders into a new document. If the problem is with the preview it seems that it "infects" the file and even merging without touching the preview button may not work.
This is on CS6 (8.0.1) on Mac.
Interesting idea about the preview 'infecting' the file. I'm sure the export behaviour changed, as I've exported PDFs from this file 10s of times before without seeing the extra 4mm (which breaks the layout) - although I've also used the data merge preview 100s of times. Will keep the new file idea in mind if this comes up again.