Rackspace Mail is the leader in this category, with 3 million paid mailboxes. They offer webmail/IMAP/POP/Mobile/Exchange hosting, a 100% availability SLA, and 24x7x365 live chat/phone/email support.

Pricing starts at $2/mailbox/month, but there's a $10/month billing minimum. $10/month is more than reasonable for a small business to spend on e-mail hosting, IMO.

https://www.rackspace.com/email-hosting