Você pode testar se os PDFs baseados em imagem também estão poluídos. Primeiro converter PDF em TIFF (com várias páginas), por ex. com ghostscript :
gs -sDEVICE=tiffg4 -o sample.tif sample.pdf
Em seguida, converta o TIFF em PDF, por exemplo:
tiff2pdf -z -f -F -pA4 -o sample-img.pdf sample.tif
Esse resultado em um arquivo PDF em que as páginas são imagens em vez de texto.
Como alternativa, se o seu sistema suportar a impressão de arquivos TIFF, tente imprimi-lo diretamente.
Há também a opção de pdf2ps
para converter PDF para PS, o que, se funcionar, provavelmente seria preferível.