Use a paid service. I use Fastmail. It baffles me every day, how HN is obsessed with Gmail as if there was no alternative and are willing to trade a minor improvement in comfort over having every email read, analyzed, indexed, profiled and put into the Ad machine. I'm also surprised that so many people use the web client and not a native client with IMAP.
I agree with noja, fastmail is pretty popular on HN.
Nonetheless, I use it as well and I'm very happy with them. The Android client is sometimes a little weird, but mostly it works and you can always use one of the many IMAP clients if you want. And I prefer their webinterface over google's
