With the release of Cyrus IMAP 2.1.2 there will be a new backend option: skiplist.
We have already moved our development system to use it and performance seems very good. I expect we'll be moving our production system to it within a few months. It should not suffer from the same problems with insert/modify operations that the flat file has and it has better list speed than DB. The only drawback is the code is kinda new. It is committed in CVS. Larry should be making a release of 2.1.2 soon (by the end of the week?). Walter