well, i decided to drop gmail because of this (at first i dropped search, but nothing else was as good at the time and search is pretty much critical for my work - and i still use disconnect, ghostery and adblock plugins, so my search and browsing in general are anonymous-ish).

i looked around for a different provider. the best i found was http://www.runbox.com/ - it wasn't as good, but it was the closest (the main feature missing was tags; their support was very good).

but in the end i ended up handling email myself (on a linux box). it's very much not the equivalent, in that i use a console client (mutt). but the part that i most needed - search - works well using mairix http://www.rpcurnow.force9.co.uk/mairix/ (very fast, flexible command line tool for searching maildirs).

unfortunately this doesn't generalise well - i can't imagine most people would be as happy using command line/curses based tools or configuring their own email services.