Originally written for a Slashdot article, but figured this may come in handy for people who read my blog...
First, setup a new account on your imap server just for archival purposes (you can setup an imap server on any UNIX/Linux distro and even Windows with Cygwin fairly easily - dovecot is a good place to start). Make sure its using either mbox or maildir (preferred).
Second, setup said account on all the mail clients you'd like to archive. Make sure you are setting them up as imap and not pop3.
Third, drag the contents of each local folder/inbox/etc to a folder on the archive specific imap account. It will take a while, but the entire contents of your mailbox will be copied over, message by message, in imap's way of doing things, then deposited by the imap server into a the local format of your choice.
You've just created flat text versions of client specific archives. Create folders, sub folders, etc and organize things in your modern client which can easily do imap. You can easily search with any numerous free packages, archive and compress permanently with squashfs, or even just leave them available through imap to search with the new Thunderbird's (3.1) global indexer.