> OCR itself is a pretty CPU intensive activity and takes a significant time to complete for many documents.
Leaving the quality part aside -- this job itself is easy to parallelize in that you can split it up by document or by page.
Open option is to run each job in Lambda asynchronously, with the input being a URL to the page or the full document, and have the job call back to you with the text of the page (or put it on S3 as a text file, or add it to a message queue, or whatever works). Regarding splitting: we've been using a python wrapper + pdfium for splitting PDFs into page images on Lambda, with excellent results.
To make the Lambda function, you'll either have to build e.g. Tesseract such that it fits into a 50MB zip, or download it while the Lambda function executes. LambCI has a set of docker containers that they've made for simulating lambda, and the "lambda:build" container makes building things easy and repeatable: https://github.com/lambci/docker-lambda. In a pinch, you can build on an Amazon Linux EC2 instance and it should work on Lambda, but you will have to be more careful about dynamic linking.
As another option: I'm not sure if it's been mentioned, but you can also try a ready-made OCR service before packaging up Tesseract, like this one: https://algorithmia.com/algorithms/ocr/SmartOCR.
So anyway, the performance part has good solutions, at least.
For fixing the accuracy: I know next to nothing about approximate string matching, but perhaps it would then be possible to do a fuzzy search over the text using something similar a Levenshtein automaton: https://en.wikipedia.org/wiki/Levenshtein_automaton.
You may also want to take a look at this: https://en.wikipedia.org/wiki/Bag-of-words_model
More broadly, I'm sure that there are text-based document classification methods that are robust against sloppy OCR. It may just take some research on the main approaches people take to document classification -- it's not my area, but my understanding is that this is typically approached with statistical methods. Otherwise your spam filter would get defeated by typos.