Another possibility is to make each message a file; my mail system on the Acorn does this. I has costs on some platforms I imagine, most seem to have a minimum file size of some sort so you can waste space easily. With disk prices as they are these days, I don'timagine that is a particularly worrisome mater. It does offer an interesting sort of security in that it is quite difficult to end up deleting parts of messages and there is something vaguely transactional about it. If the index file(s) stored the relative paths of the messages then that would presuambly map to message IDs reasonably. It might even help with avoiding the redundant loading of message left on the server.
Now of course if we had machines able to use the file system we designed at Interval, indexable by content and tags etc, this would all be much simpler. Sigh.
tim