If you choose your layout carefully SQL should be fine. Certainly you can index on whatever you like that way. You also get the potential to do clever things like storing message bodies or mime parts once and foreign-keying them into individual mailboxes (if I email 30 people a single 1M file I should only really need to store it once).

This actually looks almost like what I want out of a webmail client except it's lacking hotkeys. I don't know how people manage email without keyboard shortcuts.