Yeah, I use notmuch in emacs for my mail, and searching is way better than in gmail.

Gmail's interface is very limiting, actually. It's pretty good for a web app, and probably better than Outlook/Exchange, but when the competition is so poor it's easy to seem good.