provides some clues:
1) Search your emails for "-(label:a OR label:b OR label:c ...)" or
more intuitively search for "!label:a AND !label:b AND !label:c ...)"
2) If you are using Firefox with the Greasemonkey extension, you can
try this userscript:
http://userscripts.org/scripts/show/2283
It will add an "Unlabelled" entry in the end of your labels.
Fanis
Regarding (1): if your labels have any spaces in them, you should put
a dash ("-") in their place when you are building up your search
query.
Regarding (2): What didn't work? Did the script get installed
correctly? Do you have the right version of Firefox and/or
Greasemonkey? I'm certainly not an expert on the matter but that
userscripts.org page has various comments from others who tried the
script. Perhaps one of them applies to your situation.
Fanis
<quote>
Jaidev says on Saturday, March 04 2006
Multiple labels are not treated as unlabelled. If you see a
conversation with a label in the results, then one (some) of the emails
in the conversations hasn't been labelled.
</quote>
I've checked - this doesn't apply (isn't the problem) in my case. The
conversation itself has a label and not partial emails (as the subject
and next to it the label is displayed). I can't assign a label to
single messages, apparently.