This is a bit tricky to answer without being aware of the domain area, so this might feel like a bit of a generic or detached answer.
Two things jumped out from the question...
- "it's not always very easy for our users to find the exact document they're looking for."
Perhaps the categories are the problem?
Let's face it - it's probably not the user's fault!
I would investigate the reasons for this in more detail. When a user has difficulty finding a document that is known to exist, find out what category or categories they were wanting to look for. Keep researching and see whether some common categories are coming up that might make it onto the top level category list.
Research the domain of the documents. Are there common themes that could help with categorizing - people, place, product, price, process.
Ask a bunch of people to write down what categories they might expect a document to appear in. Do this via a card sorting exercise.
If a document might appear under Food > Italian for example, then consider whether there might be a case for also having it under Italian > Food.
Consider using multiple inheritance to have the same item under multiple paths.
Ensure categories are clearly defined and don't overlap - like in the game Animal, Mineral, Vegetable. The fewer hard decisions people have to make, the better. Trying to decide which of a few similar categories they might need to start with is hard work.
Give the user some indication of the amount of work required to explore a category. Indicate the number of documents in the category. If they really don't know where to start looking, they might eliminate a category with a smaller number of documents first.
Provide access to recent/favorite documents in the event they've looked for (and found) documents before.
2) "my perfect solution is to ... add a search bar"
That's a nice idea - possibly hard work, problematic (but possible) with PDFs, and difficult to maintain of the documents change or get updated regularly.
But you could do a search filter rather than a content search. This would be based on category name, document name, document title, and as you mentioned any tags that you may have used to for a document in the system. Tags are another maintenance headache and you have the same issues as categories. Essentially your categories are like tags. (By the way, PDF documents can have tags added at authoring time - might be worth seeing if they already exists?)
Consider searching/filtering/faceting by other criteria or metadata that make sense - e.g. maybe by size, date/age, origin, type, author, to reduce the set of categories that remain.
Both of these sets of considerations have brought me to the same conclusion:
Treat your documents like products your trying to sell them. Why not use some of these and other e-commerce style tactics to try and get the products (the documents) in front of people. You may not be actually selling them, but the principles are the same - let the user find the product with the minimum of effort.
[I did say it was going to be a bit generalized]
