Keep in mind that your privacy is only as secure as that of your correspondents. I kind of gave up on the idea of keeping email private when I realized that most of the people I write are non-techy and use GMail, Facebook etc. naively.

This is only true if your correspondents are all using the same service. If you use gmail then google knows the entirety of your email network. If you host your own mail then google only knows your links to your correspondents who use gmail, but not your links to those using hotmail, facebook, etc. (unless that info is revealed to google by putting multiple recipients in the to or cc entries in the message.)

http://www.hushmail.com/ perhaps?

although sadly: http://en.wikipedia.org/wiki/Hushmail#Controversy

thanks, I knew about hushmail, but their usability and search function are not up to par. It's funny - I'd gladly pay for a technogically sophisticated alternative to gmail, just not to have all email data with google.

If you'll give us another chance re usability, make an account & fill out this beta invite form: https://www.hushmail.com/contact/preview/

We have a new + faster + easier-to-use webmail coming in the next few months. It's a huge improvement over what we have now.

Search is still in the current folder only though, so that might not be quite what you're looking for.

(btw if anyone wants to help us build a better webmail, we're hiring PHP devs in Vancouver)

There's Lavabit.com -- a nice little place with a strong stance supporting end user privacy. Not the most full-featured web interface, but it's a nice service if you like to access with IMAP or POP.

Rackspace has a solid email hosting for businesses.

Part of their sales-pitch is "Ad-free and Privacy Guaranteed," but eventually it always comes down to a question of trust.