You can search nested labels. If you go into a sub label you should see the search box auto-populate with that label (including the nested on).
For example I have a nested label "Invites" in the label "Calendar" (Calendar/Invites). Searching "label:calendar-invites blah" searches for "blah" inside the nested label.
The issue arises if you know the message you want is somewhere under Calendar, but you're not sure whether it's in Calendar/Invites or Calendar/Rejected or Calendar/DateNotSetYet. As far as I know, it's not possible to search them all at once, just by searching under the tag Calendar.
I agree, you can construct a pretty flexible search system with the existing Gmail implementation. (disclosure: I work at a small startup trying to address email search and archive organization). How many rules do you have set up to achieve your (arguably very reasonable) workflow?
However, to perform a successful search with specific constraints, you must either:
1) Remember a keyword
2) Have a label for the particular constraint you want to use
Our little startup, SolNovus (http://solnovus.com), has been investigating how to make a couple power-user functions like this more accessible. Our priorities are:
1) Fuzzy topic search: make keywords more forgiving
2) Analysis and visualization of email graph: sift through related threads and see the impact of search constraints, represent scale and organization with more than an inbox counter
For example I have a nested label "Invites" in the label "Calendar" (Calendar/Invites). Searching "label:calendar-invites blah" searches for "blah" inside the nested label.