It finally seems to be working. I've done some testing now and it seems to be working fine. If you have time, see if you can get it to break (especially with INDEX=memory or by manually modifying the maildir).
The UIDs are kept in Courier-compatible dovecot-uidlist file (so "mv courierimapuiddb dovecot-uidlist" should work). The great thing about this code is that we never wait for lock. If we can't lock, we simply use the old uidlist file to sync whatever we can, which should be everything but the very newest mails just being delivered and processed by another Dovecot. Of course, if they share index files, we're still blocking there.
I named the file as "dovecot-uidlist" instead of ".uidlist" because I finally realized that files beginning with dot conflict with the mailbox namespace. I should rename .customflags and .subscriptions files as well. Also if I move .imap.index* files into root dir, I'll have to rename them too.
new/ directory is now scanned every time to see if there's new mail. cur/ directory is scanned if index file's timestamp differs from cur/ dir's timestamp. uidlist file is reread if it's device/inode changes.
You can get the sources from either CVS, or 0.99.9-test2 from http://dovecot.procontrol.fi/test/