Суть проблемы в том, что такой pdf содержит шрифты, в которых русские буквы находятся не на своих позициях, а на почти случайных (на каждую встреченную букву дается новая позиция). Позиции в шрифтах разного размера не совпадают и т.д.
Графически распознавать не хочется (хотя советы по графическому распознаванию тоже интересны)