Puede probar si los PDF basados en imágenes también están contaminados. Primero convierta PDF a TIFF (multipágina), p. con guión fantasma:
gs -sDEVICE=tiffg4 -o sample.tif sample.pdf
Luego convierta el TIFF a PDF, por ejemplo:
tiff2pdf -z -f -F -pA4 -o sample-img.pdf sample.tif
Esto da como resultado un archivo PDF donde las páginas son imágenes en lugar de texto.
Alternativamente, si su sistema admite la impresión de archivos TIFF, intente imprimirlo directamente.
También existe la opción de pdf2ps para convertir PDF a PS, que si funciona, probablemente sería preferible.