Использую я Okular (ибо Kubuntu 8.10, KDE 4.2), но проверял и в gv и в Adobe Acrobat Reader.
Один файл рендерится как должно, масштабируется идеально и вообще - великолепно все. Второй же - в варианте просмотра 100% еще более-менее читабельно, но стоит приблизить - точки, из которых буквы состоят видны становятся =\
Оба файла качества «изначально компьютерное», так что - ни на какой OCR не грешим.
Прикладываю вывод pdffonts, для анализа. Сначала вывод для первого файла, потом для второго.
P. S. Эти файлы взяты для примера, файлов как первого, так и второго типа - достаточно много.
Вывод pdffonts - http://www.everfall.com/paste/id.php?5bxbmixj5ve8