The IMAP server Dovecot proves that this short of on-the-side indexing can work well. You can keep you email in dumb old mbox files (on big file for each folder) and dovecot creates indexes on the fly to provide lightning fast access to the fields it indexes.
_________________________
Remind me to change my signature to something more interesting someday