Ask HN: Best mail hosts?

I've been trying to ween myself off of Google-hosted products, even opting to pay for things rather than get them for free. Gmail is the last big dependency of mine.

Can anyone vouch for a mail hosting provider? The things I'm looking for are:

* Reliability (uptime, durability of data, long term viability, etc)

* Security (preferably MFA, access audit trail, generally secure reputation and history)

* Good search (yeah, this seems to be the deal breaker) -- I don't do labels/rules, I tend to try to do zero-inbox, but rely on search to dredge stuff up later if I need it.

* Any kind of support for multiple identities, and custom domains, would be nice, but not required.

Anything out there that may fit the bill?

Or is anyone else in search of something similar and also coming up empty handed? Is there a niche looking to be filled here?