E-mail Service Recommendations?

The e-mail configuration on my server is the most complicated set-up we have on the box, and it’s also one of the most resource intensive (bayesian spam filtering). A big load of e-mails being accessed by one of our users over IMAP recently brought the box to a crawl. I’m looking at moving to a more powerful server, but reconfiguring the e-mail set-up is the biggest hurdle to making such a move. Because of this, I’m considering outsourcing e-mail entirely.

I’ve had a FastMail account that I’ve used for SMTP access since January 2003 and it’s been pretty reliable. $70 for 2 years of their Enhanced account certainly seems reasonable (~$.10/day). I’d need to spend another $8 to upload my current ~1GB of mail to their servers – I’m OK with that too. The only concern I have is not being able to back up the mail directly from the server to my own backup system (though I could have everything sucked down locally and back that up with my little system).

Does anyone else have recommendations for services they’ve tried and liked (must have IMAP, that takes Yahoo Mail and Gmail off the list)? Or perhaps services they’ve tried and would recommend staying away from?