Thanks for the interesting suggestion, Alexey. I am unable to tell for sure, but it may well be that flattening transparency is related to my problem. The images were Graphics objects, not Graphics3D.
I am not sure that I can use your method. I don't know how LaTeX does it, but it needs to be able to identify certain strings of text in the EPS-file as such for the psfrag-substitution to work the way it used to (substitute a user specified string with a TeX-command). The rest of my document will be typeset by LaTeX, and using fonts other than those in my TeX-system is not an option.
My testing confirmed that Mathematica was changed for worse in this sense when moving away from version 9. I would also like to know why Wolfram did that? Or is there an export option to go back to this (not unlike the option to temporarily go back to version 5 graphics that existed in some versions for the purposes of backwards compatibility)?