This sort of stuff happened all the time when I worked in tech support for ad agencies. Printing font problems seemed to be 99% of the job, some days. PDFs helped — but only of the person making them remembered to embed the fonts. Usually you would simply make an EPS (encapsulated Postscript file), which would work most of the time — as long as the receiving printer had sufficient memory for huge print files. Can't tell you how many thousands of times art directors who should've known better would just send Quark or PageMaker or (later) InDesign files without the fonts. In fact, there were (are?) preflighting programs designed just to solve this exact problem. They'd look at your files and determine: Are your fonts there? Are your images there? How will this print? etc., etc.
There are indeed PDF preflight tools to this day. E.g. on Linux you can run `pdffonts` and check that everything is embedded. I believe it's still very common, to the point that my local university's PhD thesis print delivery checklist includes it.
