Well, mbox is a pretty simple plain text format for storing mail. I know that you don't have a need for "mailbox" formats, but I can't think of a simpler way to store mail messages.

It ticks your other boxes too. You can use grep on in and there are Perl modules for dealing with it too.