We had a pretty lengthy discussion about this before the summer, and the consensus seemed to be that a fulltext-based approach looked most viable. I actually wrote an extension that does that, and promised to release it soon; that was quite a few months ago, and I never got around to it. I'll release it properly when I have time, which will hopefully be before Christmas :D
The code needs some tweaking and refactoring, though. It's pretty tightly integrated with the article text search (both functions in one form) and has all kinds of weird features, because the guy who paid me to write it wanted them. It also doesn't support three-letter word searching (which core does these days, using a prefix hack), which is pretty bad since categories with short titles (or stopword titles) won't be found either.
Roan Kattouw (Catrope)