Virtually everything supports MBOX (which, modulo a few gotchas, is just a concatenated file of the text-formatted RFC822 messages as they went over the wire). Most mail clients support it. Many mail servers do to, so for example you could drop this into /var/spool/mail on a AWS instance, run a default dovecot install, and hit the server with any IMAP client.

mbox is a standard email storage format. It's not ideal for a live email system, but not bad for archiving or for import/export purposes.

You can import mbox into variety of desktop email clients and, using IMAP, upload them to web-based UIs.

Here's how to move off Gmail to Rackspace (not free) email, I've done it last weekend [1]:

  - Enable IMAP access in Gmail
  - Add Gmail account to Apple's Mail.app
  - Wait for Mail app to sync.
  - You have a full copy of GMail archive on your computer now
  - Select all messages in Mail app, and select Message/Copy To
  - Pick Rackspace inbox and click "OK"
  - Delete all your email messages in Gmail, purge Trash. 
  - Done.

I also exported Gmail labels into separate mbox files just in case.

[1] http://www.rackspace.com/email-hosting/webmail

P.S. For anyone wondering, I moved off Gmail because of two reasons:

  1. New compose window was impossible for me to use.
  2. Security issues.

I've done similar things a variety of times, the download -> copy -> paste routine is pretty simple. So far I've never had a problem with it (even moving 100k or so).

Mac Mail.app can import mbox files but the default storage is emlx if I remember correctly for Spotlight indexing.

Thunderbird should also import mbox

I am a bit paranoid about my Gmail account so I use the Mail.app to download the emails and then I back it up. If my account gets locked for whatever reason, 'Download Data' option is not going to exist. So better to backup through other means as well.

Probably most desktop clients. You can import an MBOX file to Thunderbird with the ImportExportTools extension (which Mozilla links from their KB):

https://addons.mozilla.org/en-US/thunderbird/addon/importexp...

Many desktop mail clients support mbox format. Thunderbird uses mbox. There's also a script (I'm sure there are many scripts that do this) that take mbox files and upload the mail to an IMAP server. (http://imap-upload.sourceforge.net/)