Any decent database should be able to handle thousands of records with the searching you describe, so it’s really just a matter of finding either someone who will develop the tool for you or one that fits your needs and is already made.
You didn’t mention if the documents were hand written or typed, if any sizable portion is typed you might want to look into OCR solutions if you haven’t already. I would imagine you might be scanning the documents, so for typed documents it could take care of everything at once for you. They usually include some sort of storage solution with search and a lot of other features.
If you need to find something more flexible for hand written documents, I found this Manuscript Transcription Database project at the University of Virginia. It looks like an older project that might not have been updated, but might meet your needs as it stands or have grown into something since.
If you have access to someone familiar with web technologies (PHP specifically) it looks pretty easy to set up and is custom made for the type of work you’re doing.
Here’s another along the same lines called Document Database that seems to rely on something called BibTeX that I’m not familiar with for some of it’s search and classification. Maybe that means something to you?
Good luck with your search. There are quite a few ways you could go and I would imagine the next round of people going through those documents will be happier with any of them than they would be with binders of printouts.