I had over 80,000 un-labelled messages (6.8 GBytes) in GMail. I wanted to delete them.

Guess what – there’s no way to select messages without any labels. Google’s own help files say “There isn’t a search operator for unlabeled messages“.

It seems I’m not the only one with this problem. After a Google search on the problem, I discovered that the only known method is to search using the “-label: ” operator that finds messages that don’t have a given label. If you have 4 labels you can search on messages that don’t have any of the 4 like this:

-label:Label1 -label:Label2 -label:Label3 -label:Label4

or

-label:{Inbox Outbox label1 Label2 …} // only for single-word labels

Which is fine if you only have four labels. I had hundreds of labels.

Google support said there was no way to delete just the unlabeled ones, except by hand.

But there is.

1. Install Google Apps Sync for Microsoft Outlook®.
2. Install Outlook (I used Outlook 2003).
3. Synchronize Outlook with the GMail account (this may take a long time – days – if you have a lot of mail)
4. Exit Outlook (important!)
5. Go into GMail, select “All Mail”, click on “Select all messages that match this search”.
6. Delete all the mail in the GMail account.
7. Run Google Apps Migration for Microsoft Outlook® (this gets installed automatically when you install Apps Sync)
8. Migrate your Outlook .PST file (the account you synced in step 3) to your GMail account.
9. Restart Outlook. Let it sync with GMail (may take a long time – it’ll transfer the entire account).

You’re done. You can un-install Outlook now if you don’t want to use it (you don’t have to; it’ll stay synced with GMail).

I did this. It works. Now I have only the 792 messages that actually have labels.