In apple mail, I can search all my mailboxes for all my accounts in one search and it's pretty much instantaneous. Most of my email accounts are hosted in gmail, but I generally use Apple Mail to access them (the only times I go into the web interface is for the account I use for submitting writing where I apply multiple tags to each message indicating publication/piece submitted/response type or to clean out the spam folder since I worry a little that if I delete messages from Apple Mail I might be inadvertently telling gmail that the spam wasn't actually spam).