Interface advice: Categorize in many many categories

I have a client that categorizes their documents.

Great, you think. Well, they categorize their documents in one or more of almost 3,000 categories. That’s something that’s hard to build a nice, simple interface for.

Here are some possible approaches that I and the few people I’ve asked have come up with:

1. Present a single page with all 3,000 categories, displayed hierarchically, each with a checkbox next to it. Yeah, that’s what we have today. Let me just say that it doesn’t work great, and that we didn’t start out with 3,000 categories.

2. Let people navigate to the category first (think the Yahoo! directory) and add the document there. We have that, too, but that only helps you choose the first cateogry, not the additional ones.

3. Present a series of drop-downs. First we show you one with the top-level. When you choose there, we show you another one with the subcategories of your first choice. We keep doing that until there are no children or you choose “Add category”. Yes, documents can be added to any category, including those that have subcategories.

4. A variant of this is to use multi-select boxes instead of dropdowns, mimicking the OS X finder interface.

5. Use a dynamic Windows Explorer-style tree, like XLoadTree.

6. Live substring-based search. Good if you know what you’re looking for, not good for browsing. And it short-circuits the structure, searching just the categories and not their relationship. This seems useful, but it’s an add-on to another solution, not a solution in itself.

I’d like to ask your advice. Please send me your suggestions. Screenhots or links to interfaces that solve this well, whether web or not, would be fantastic. Post in the comments or email me, and I’ll put it up and share.