I am one of the few people I know who pays for e-mail. And I'm very happy to see my Gmail account get 3 e-mails a week. So far, I've been using GoDaddy as an e-mail host, mainly because it came with the domain purchase. I'm really not happy though, and I'd like to switch.
What are your suggestions for a paid e-mail hosting service? Reasonable storage, IMAP access, and reliability are the most important.
I read that Fastmail was a good contender. Any other options?
EDIT: Forgot to say that some of the e-mails that I send from GoDaddy end up in Gmail's Spam folder, which is of course terrible. I read that this could be avoided by a properly configuring DKIM. Thoughts on this would also be appreciated.
If calendaring is important you should check out Office 365, lots of storage, syncing between devices, and depending on the SKU, you can install the latest Microsoft suite locally on 5 devices.
The industry leaders in the US are Rackspace and AppRiver and their success can be directly attributed to their bend-over-backwards support so you won't go wrong with either. Rackspace also has a Google Apps offering if that's more your flavor.
If the only reason you are compelled to leave GoDaddy is related to the spam issue mentioned, you can also check out their Office 365 offering, it's hosted by Microsoft so upgrading should eliminate this issue.
Email is pretty much a commodity nowadays, so if support isn't a big deal there are hundreds of smaller providers. Look for Hosted Exchange, it's like Office 365 but without the Microsoft Office suite (although with the way the industry is moving they'll probably force upgrade you to Office 365 within the next 2-5 years anyway).
Disclaimer: I work for a startup managing our large mail provider partnerships, I'm recommending these companies because of first hand experience - (despite their size) they're as passionate as we are, the best at what they do, and relentlessly focus on providing outstanding customer experiences.