P.S.: Just got a message on my Commons talk page about the "+incategory:" search function.
- This is based on the Lucene index, right? How often is that updated?
It is updated daily. As already pointed out, it doesn't do transcluded categories, but just looks at Category: links within raw article wikitext.
- Is there a decent interface/special page for that? It's a pain to
enter this manually, and I doubt many people know about it
Nope, no interface. I've pretty much made it just because it was easy to do, and doesn't really take up any significant space in the index. If one dared to make a category intersection frontend it could possibly be useful for testing.
However, as discussed before, making an efficient and easily-integrable-into-WMF-type-setup backend is not exactly straightforward.
Cheers, Robert