Всё делается за несколько минут при помощи программы ABBYY FineReader 11, причем, практически автоматически без мудоханья с онлайновыми сервисами и без потери (а это главное) качества.
Открываем в ней документ, "распознаём" его, выделяем все страницы - "Редактирование изображений" - "Отразить". Как только операция будет закончена - "Файл" - "Сохранить документ как" - там выбираем формат pdf