Some of the issues around the structure of categories have been both contentious and promising for a long time, 2 years or better... (see http://en.wikipedia.org/wiki/Wikipedia:Category_math_feature, and many links to category intersections / category math on meta)
I *still* think categories as tags is one of the most promising applications of a wiki, as opposed to hierarchical categories like dmoz. We currently seem to be doing some of both (the administrative categories are essentially tags, while many other categories, ie "Norwegian composershttp://en.wikipedia.org/wiki/Category:Norwegian_composers" which is several levels down from the high level musicians category, etc.) and that's really pretty cool.
I think we should *embrace* doing both types of categories, because we can in the wiki structure, it's not an mutually exclusive way of doing things. We can make everybody (sort of) happy. The hurdle then becomes writing code efficient enough to sift through all the records to find what you want.
Now, as I mentioned before, I don't' have experience with writing code to deal with zillions of hits, but I think a simple implementation of "find all pages belonging to category1 AND category2" is accomplished using a sql like this pseudocode: "select pages, count(pages) as count where (category='category1' or category='category2') group by pages having count='2'"
Again, I'm not efficiency expert, but that puts the heavy lifting on mysql and is pretty straightforward. I've currently written an implementation that is a bit more full featured, messy, and inefficient than that.. but I'd be happy to pitch in to a new one (I'm still on mediawiki 1.4x, sshh!)
Best Regards, Aerik