With Gmail, I am concerned that I could get arbitrarily locked out of my account with no recourse. Also, I wouldn't mind moving away from Google in general to support a more decentralized internet. If it is based outside of the US, even better. But these considerations are secondary.
So I am looking for something secure, reliable, and usable (good search, not getting overrun with spam) that I could use for the next few decades. Privacy is only important insofar as reasonable security is concerned (vague, I know, but my point is that practicality is more important).
What do you use and what have been the pros and cons?
The only con I see is: there is no way to add separate 'mailboxes' to it. I can register multiple addresses, but it's still one account, thus one mailbox.