So less than a week after I unveiled my ghetto fashion search I just happened to visit the wiki Version page (which lists all of the wiki's installed extensions), and what should I find but:
That's right, our illustrious wiki overlords have heard my pleas and graced us with the official (not ghetto) multi-category search extension! Unlike my version this one allows you to search across five(!) different categories at once, without a risk of slowing the site down. Also, the official tool lets you specify three "ignore" categories, so if (for instance) you wanted to find a "Fashion: Leather" Shaman hat that isn't from Velious, that's possible now too.
There are two small downsides: 1) you have to type the full category name in (there's no drop-down), and 2) you have to capitalize the category name correctly (eg. "Fashion: Leather" not "fashion: leather").
But those are some pretty small downsides, so let me be the first to say:
Thank you Rogean (and the rest of the staff)!
P.S. To make the new search easier to find (after this post fades) I've added a link to it to the bottom right area of the wiki's front page.