I think your mention of "a lot of different variables" is significant.
To name only a few obvious ones that we have to deal with: there is the Distiller packaged with FrameMaker as against that in the full Acrobat product; the order in which programs are installed; the order in which updates are installed; different PostScript drivers installed by our network managers for a variety of printers, plus a centralised (non-Adobe) PDF production tool ... and that's before we get on to fonts, the options within FrameMaker under "Generate Acrobat data", the options within Distiller, etc., etc.
Like you, our workstations are not used exclusively for FrameMaker/PDF production. It's not practical to control the environment strictly, and life is too short to carry out extensive "does this work?" tests.
One colleague uninstalled and then reinstalled Acrobat 8, to make sure it was the last tool put in place. It worked, for about a week. Then something changed (what?), and it's back to crashing Distiller. Today she installed PDF Creator.
I am just happy to find a working solution, and will stick with it until it fails. Luckily almost all our PDF production is on a one-off basis.
I hope you find a work-around for your problem. Sorry I wasn't much help, but I couldn't resist expressing some of the frustration we are feeling.