One idea:

Use Google email but from a custom domain -- it doesn't back-up your email, but you can update the DNS to a new provider if you get locked out of Google's services. This means you can still recover accounts, use the same email, etc after a brief disruption, instead of totally hosed.

It's not a total solution, but it does mitigate some problems, which makes Google's policies easier to swallow. (If you do separate email back-ups, then you'll only lose the emails since the last back-up.)

I'm in the process of switching to that set-up (partly because of these antics; partly because of other concerns).