I have had an awesome experience with https://mxroute.com/. The owner takes deliverability very seriously and I have never had an email go to spam. I would recommend it.
+1 for MXRoute if you're just looking for an affordable alternative to Google Apps and not some fancy API. They bill by storage and not by the number of accounts, and they offer discounts around the year if you look around. Also don't be fooled by their frontend that looks like some run of the mill shared hosting. Their backend is absolutely professional.
I had heard of mxroute previously, but for some reason, i only thought they focused around transactional email...like sendgrid, etc...and not what others might refer to as conventional mail hosts. Their price is really compelling, and the honesty of their documentation is refreshing! Take a gander at some of their commentary around hosting calendars, contacts for example: "...Just know, that’s not where the bulk of our time and energy is going." [https://mxroute.com/docs/#/General/Do_You_Sell_Calendars] Granted i have the need for email as well as calendar and contacts, but damn that level of honesty is compelling for me to at least consider them for my short list. Kudos to the MXRoute folks for being honest!
I second PurelyMail. Their price schema is based mostly on mailbox storage size, and I believe I paid under 10$ for the last two years of hosting some catch-all mailboxes for multiple domains.
My favorite thing about MXRoute is the super simple rate limits that you can configure when adding a user. I use it on devices for notification e-mails and being able to limit those logins to something low like 5-10 emails per day is awesome. It really minimizes the damage if something goes haywire, a device gets compromised, or a device gets stolen.