Best way to organize a document search

Our company has hundreds of business-related PDF documents in a repository built and run by a 3rd party company. These documents are organized into a typical category/subcategory hierarchy so I can easily retrieve all documents under "Food > Italian", for example, but with the number of categories/subcategories and the total number of documents, it's not always very easy for our users to find the exact document they're looking for.

I've been tasked with coming up with a way to make this process easier. In my mind, my perfect solution is to display the category/subcategory structure (as we do now) and just add a search bar at the top of the page where a user can type in a piece of text from the document and the application retrieves the documents containing that text.

My problem is that searching PDF content isn't the easiest thing in the world and the 3rd party company who built the repository has made it clear they're not really interested in a major re-tooling initiative.

The documents can also be assigned tags and I could potentially create a tag search but all tag search interfaces I'm familiar with aren't user-friendly enough for the typical user and you bump into the same issue of which tag is the correct tag for the document you're looking for.

Here's my question: What is the best way to allow a user to search for documents they can't find using the standard category/subcategory method?