A couple ideas come to mind. I bleieve you said the fonts are installed, so I suppose embedding should not be required, but perhaps ensure fonts are embedded as a test. I have also noticed that Word's Save As PDF does not always result in embedded fonts even when the option is selected (at least, format reviewers have told me this even though I know I did it). Perhaps try Adobe Pro on the highest setting and that will auto embed. I believe you said you were using Print to PDF, which might not have this issue, but I mention it just in case.

Exactly spacing is one option but can present a host of formatting challenges in the document, depending on what is going on. Of course, all those challenges can be navigated, and, in the end, you would have more control. Personally I prefer not to use it because I find addressing those spacing challenges within my styles tedious. One exception I have run into is when the document contains many foreign or nonstandard characters, which can create uneven line spacing (e.g., traditional Chinese characters creating more vertical space in just those lines, which Exactly spacing can address). If that is part of the issue, you could always use exact spacing for the couple paragraphs where that happens and adjust the before/after spacing as needed and then use another spacing setting for the remainder of the doc. If you have a ton of such character, perhaps Exactly spacing is well, exactly what you need.

In general, I have found pdf generation to be inconsistent, as I imagine those links Charles posted discuss. Adobe seems to result in a document that is consistent for most purposes, except when a format reviewer measures things to the mm and forces me to play with settings.

Good luck, and if you find a solution, please post for future reference if you don't mind.