Finally today, I have worked out a clean solution which does not offend me.
Firstly, it turns out that most of the problem is actually coming from the embedded graphics. pdflatex itself does seem to satisfactorily embed most fonts, although you can force it to if necessary, and there are various sites around which say how to do this. But this doesn't help included PDF figures which don't have fonts embedded already. For xfig and so on (another tip: in xfig, the "view --> portrait/landscape" option will fix it so that your figure is output with the correct orientation if it's coming out twisted when you export it), just export direct to PDF and it should work. But some figures are generated in eps format, and then converted to PDF. Usually, I use epstopdf to do this, since it gets the bounding box right, but it doesn't seem to do the trick. So here is what you need to do: issue the command
and then all will be well. You can work it out for yourself why this will work.