I've been looking for a functionally equivalent alternative to gmail largely because I fear ending up in a similar situation. I'd like to host my email with a company that has remotely competent and caring support.
What are the best services?
And no thanks to cloud haters - I will not be setting up my own imap servers.
Rackspace Email (formerly MailTrust). The service itself is excellent (IMAP/POP/Exchange hosting, spam filtering as good as Google's, a 100% uptime SLA, daily backups), and it comes with Rackspace's well-known 24x7x365 phone, chat and ticket support. I've hosted my mail there for 7 domains for years.
When I was doing IT consulting before starting my company, we used to contract a great Florida-based company called AppRiver for hosted exchange (plus IMAP and POP, naturally) for some of our clients.
The service was excellent, and their customer support was even better -- always extremely friendly and very responsive.
I used to use fastmail but switched to google as their interface fell behind the times and I wanted features they didn't have. Perhaps I should look again.
What are the best services?
And no thanks to cloud haters - I will not be setting up my own imap servers.