I used to use Gmail and never could get search to work well in it. IIRC, it wouldn't even stem words properly. I hope that's changed since. Nowadays I use FastMail and its search is pretty good. But unlike Web search engines which tailor results based upon your history, email search is pretty naive even though I usually have a precise context in mind.
