Excerpts from Brian May's message of Mon Aug 09 01:59:16 -0400 2010:
> How do I search for all messages not containing a label? I tried:

Looking at http://xapian.org/docs/queryparser.html, it looks like "pure
not" is disabled, at least in my sup installation. It also seems like
booleans *must* be in ALLCAPS to be recognized.

Thus:

NOT label:mylabel   - gives a syntax error
not label:mylabel   - is 'not OR label:mylabel' [searching for the word
                        "not" or for the label]

I'm getting some results from a search on 'label: NOT label:mylabel',
though I'm not sure if the results I'm getting are correct for what
you're looking for.