Tim, aren't you kind of the point guy for the lucene search? Would you be up for setting up a categories index? I don't know how the update works (I think, from what I've read, that it does a big index regeneration on some kind of schedule, but I really don't know).
We use incremental updates nowadays, since the complete rebuilds where unstable and would fail or hang from time to time... The dump-then-rebuild category intersection index would likely suffer from same problems.. Keeping the index incrementally updated might not be as straightforward, as it would need be integrated with job queue in some way.
My guess is that trying to make category intersections through any other external service would suffer from same problems, and that making interfaces for lucene or something else should be easy enough with a stable update scheme figured out.
r.