Potresti verificare se anche i PDF basati su immagini sono inquinati. Prima converti PDF in TIFF (multipagina), ad es. con ghostscript:
gs -sDEVICE=tiffg4 -o sample.tif sample.pdf
Quindi converti il TIFF in PDF, ad esempio:
tiff2pdf -z -f -F -pA4 -o sample-img.pdf sample.tif
Ciò si traduce in un file PDF in cui le pagine sono immagini anziché testo.
In alternativa, se il tuo sistema supporta la stampa di file TIFF, prova a stamparlo direttamente.
C'è anche l'opzione pdf2ps per convertire PDF in PS, che se funziona, sarebbe probabilmente preferibile.