I strongly recommend against IMAP, it's an email only protocol which means your contacts and calendars will not sync between devices. E.G you send a meeting invite to a customer from your desktop, you're not going to be able to check it from your phone during the day or on your way to the meeting. I live and die by my calendar so this is a deal killer for me, although if you don't use calendars or contacts much it may not be for you, IMAP is certainly less expensive.
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.