I use the Maildir format for storing my mail now; it's very convenient for command-line and programmatic manipulation, and it's safe even over NFS. However, it can be quite slow to load a large mailbox.
Some Maildir-using tools (Gnus, mutt and dovecot, for instance) cache the headers read from the Maildir, but there's no standardised way of doing this, so you end up with multiple caches. A standard way of doing this should be proposed.
One option for allowing compact storage but safe updates would be to keep a journal of changes to the mailbox, and only update the "main" part of the mailbox periodically (say, when the journal reaches a certain size).
Jamie Zawinski has an article describing the format used for mail summary files for mbox-format mailboxes in Netscape Mail.