In my experience over the last 7 years they've been rock solid, no lost emails that I can discern, only 2 or so short incidents when they were down for a little while for whatever reason. Storage reliability might not be quite as high as for Google, given that one meteorite in the right/wrong part of the North Atlantic would take out their NYC and Amsterdam colos, and no doubt the Iceland one they're setting up now per recent email, see https://www.fastmail.com/help/technical/architecture.html for lots of details.

On the other hand, they're a lot more transparent than Google, their special sauce does not include their infrastructure, most of which is open source or they've open sourced, and no doubt due to their singular focus and relatively smaller size you can get contact real people rather easily, sign up for updates on their software and infrastructure, etc. Google is so big that, as you've discovered, they don't have to care.

I'll second the FastMail recommendation. I closed several Google accounts and migrated them to FastMail a few years ago and it has been a good experience. The UI is very much faster and spam filtering is every bit as good as GMail's was. No complaints about uptime, either.

I wish more people knew about rollernet.us . They're incredibly excellent as an email service provider for technical users.

I'd definitely recommend Fastmail. Fast, clean interface, easy to use, very customisable (including wildcard mailboxes), and great support. They've got a really interesting blog [1] with some technical content on there as well.

[1] http://blog.fastmail.com