I am interested in a Linux FOSS solution, by the way.

I need a way to search through old email messages quickly and efficiently. 
I would use this for listserv archives and, I hope, for personal email.

I think the best approach would be to create a database containing every 
message.  Every field would be individually searchable (From:, CC:, To:, 
message body, header, attachments).  Someone must have developed something 
that can parse a collection of messages this way using mysql or somesuch. 
Anyone know?

I'm not sure how search results should be displayed but one option would 
be to use accession numbers to allow display of HTML (a la MHonArc, say) 
or the original text of the full message.  I can think of some neat tricks 
that should be possible (e.g., generate mbox on the fly), but I don't know 
if this has been done.  The data could be stored in the database only and 
messages could be reconstructed from it, or individual messages could be 
stored as files (MH format) and the database could return links to those 
files in response to a search.

I have some experience using MHonArc to make this kind of archive...

http://taxa.epi.umn.edu/~mbmiller/sscpnet/20070724_digest/threads.html

...and I have used WebGlimpse to search them:

http://taxa.epi.umn.edu/bgnews/

But I'm sure there are far better ways by now.  I put that stuff together 
back in the late 1990s.

Threading is an important issue and I haven't thought about that enough. 
It could be handled by linking to a threaded archive like the MHonArc 
archive I just showed.

What are your experiences?

Mike