I think I may have found the origin of the problem. Using PDFMaker on an original Powerpoint file from the same company, I got the following Distiller error:
%%[ ProductName: Distiller ]%%
%%[ Error: Frutiger-Roman cannot be embedded due to licensing restrictions.]%%
This is the same font that is coming out as garbage characters when copied-and-pasted.
Are there certain fonts that can actually prevent PDFMaker from embedding it? What ends up in the PDF then? It still looks OK, but characters copied from it come out as garbage, also visible in search engine results.
What's the best solution? Recommend the company doesn't use that font anymore? Get them to use a different license of the font that'll allow PDF embedding? Some kind of font substitution solution?
The first thing I'd try is contacting the font vendor to see if they offer a version of the font that does allow embedding. If not, then avoiding that font or font vendor seems to be the answer.