When searching for mail in Mail.app with a Gmail account, every instance of the mail shows up with every Gmail label, especially in the Bin label, since Apple mail autosaves drafts as you go along, there can be 50 instances of a single mail just in the Bin folder.
This makes searching impossible.
So I'm trying to turn off those labels in Gmail but no success so far. I have disabled "Show in IMAP" option in the Gmail label settings for all those labels then deleted all the cached items in ~/Library/Mail/V2 and restarted Mail.app but that didn't do the trick.