I've only been a customer of FastMail since August, but I strongly echo alaithea's recommendation.

I use the web interface for preview and POP to Eudora for the real thing. Pretty much total satisfaction. You also get space for a static web site and file sharing. Pay enough (but not much) and you can use your own domains.