Boy, I hate to pull another "me too"... but Fastmail is amazing. I've got my own domain for e-mail hosted with them and I have been extremely satisfied. I'm a fairly heavy e-mail user and I'm very picky about folders, mail filtering and rules, etc.
I have only two (very minor) complaints:
* They don't let you put large files (> 100MB) on your included web space, even for their "Enhanced" users. I'm not sure why this is and it's a little bit annoying, but I'm not using them because of their web space, so what they do provide is a bonus. You can also set up photo galleries (very basic, but meets my needs), an "uploader" or just plain web space, with and without password protection.
* If you have your own domain (I think they give you a subdomain you can use in the same way if you don't), it will automatically route a@domain to the IMAP subfolder "a" if it exists. (Similarly email@example.com goes to the folder b.a) Unfortunately, there's no way to create these mail folders "on the fly" based on incoming mail. For example, I'd like all mail to firstname.lastname@example.org to go to the Lists.something folder and create it if it doesn't exist. There's no way of doing that automatically so I have to manually create the folder when subscribing to mailing lists. Enabling a feature like this would probably result in a DOS attack, so I can understand why.
Anyways, that probably gives you an idea of how extensive their service is.
Oh, and here's the obligatory referral link: (sent.com is one of their many domains to choose from)