It's pretty easy to setup your own domain if you don't mind it being someone else's server. I first used one called ZoHo, you just need a domain and a txt record to validate control as I recall and they'll do the rest for free. That was a number of years ago though so it may have changed since.

Anything? Carrier pigeon?

Outlook

I'm using a combination of Postfix and Cyrus IMAPd.

Granted, probably not what OP was asking for, but privacy wise, this is almost certainly more water tight than any of the other options.

I like skiff.com you can forward your Gmail address to it and make email aliases for free.

Zoho is a good alternative.

I use Soho, supports custom domain, plenty of good features, it's like £12 a year and EU based / privacy focused.