How about handling complex searches as a chain? I essentially do that right now with folders. I create a folder for one search, move all the results into that folder, and then do another search. The second search is either a filter on those results (useful when I want to run multiple filters on the same results), or a new search which I then merge with that search by dragging the new results into the same folder. PP could facilitate this with the ability to create a temporary search folder on-the-fly.
The way I see it, there would be an "add terms" command (maybe just a "+" sign like in the Apple Finder when doing complex searches, but with functionality more like what happens when you option-click on that button). When clicking this, a temporary folder would be created with the current search, and a new search box would appear below the current search. There would be some kind of "and/or" switch on the left side of the search box as well. For me it would be important to allow filters to be used here as well, so that one could also do complex filtering.
It seems to me that this has several advantages - the interface is hidden from users who don't want it. It works essentially the same way it does now if you were to create a folder and do multiple searches, but simply facilitates that process by creating a temporary folder and showing both searches together, along with an and/or button.
I hope this idea makes some sense, since it would be great to have the ability to do more powerful searches. (I would also like to be able to save these complex searches with something like a "Smart folder" in OS X.)