Agreed, with the slight modification that rather than a query builder with lots of mouse selections and so forth, I'd favour a search box in the style of gmail. So for instance, you might type "tag:banana security:public" as text. Booleans allowed, etc - all combined with the current full text search that paid members get.

Whatever the UI, I suspect this is a fairly major RFE, and I don't know what the database implications might be, but it'd definitely be nice to have.