I just sent in the following suggestion. Do you guys think this would be useful?

"Include the label text as part of the message text. Say I want to search for all my e-mails that have the label 'notes to self' but do not also have the label 'MBTI'. Why can't I search for "notes to self" -mbti and get all those e-mails?"

Although you can, under Search Options, search inside a label, you cannot specify to not include a second tier of labels.