I've been testing migadu[0] since a ShowHN about it a few weeks ago. So far the service is awesome! It maches all of your criteria, plus, for a flat fee (it depends on outbound emails/day actually), you get:

* unlimited domains, mailboxes, storage space

* a very well-thought and honest service and UX ( I encourage you to read their "benefits" and "drawbacks" pages)

* a very responsive and helpful customer support

* hosting in a privacy minded country

0: https://www.migadu.com/en/index.html

I use Office365 "Business essentials" for wormhole.network

It was surprisingly cheap and it includes other stuff like 1TB OneDrive and OWA is quite cool (even though I use Outlook or Mail, depending if I'm on my main computer or not).

I have only one inbox, but a few aliases, including some for a second custom domain. As far as I can tell I haven't been charged extra apart from what they advertise here: https://products.office.com/en-gb/business/office-365-busine...

Have a look at Yandex Mail for Domain (free)

https://domain.yandex.com/domains_add/

Rackspace Mail is probably the leader in this space, with over 4 million paying SMB users. It meets all your requirements, including a 100% uptime SLA and 24/7/365 live support.

https://www.rackspace.com/en-us/email-hosting/webmail

I just saw a Show HN post about Migadu.com and signed up. I've been very happy.

Pricing is excellent. They let you add unlimited domains, mailboxes, aliases, etc. The only discerning difference between plans is the number of outgoing messages every day across your entire plan.

I've used Google Apps (G Suite) for hosting kje.ca email for a long time and it's great. I'm luckily grandfathered under the free plan but I'd pay $5 a month for the service if I had to.

Fastmail is awesome and fulfils all of your criteria I believe.

FastMail does not offer any type of phone support.

I was using the same now switched to G suite