Looks like maildir can't be used very realiably without quite a lot of locking. Writing and scanning the directory would have to be locked, but reading wouldn't (as long as the file hasn't been renamed which would require scanning to find it). So much for "no locks needed"..
The problem is that opendir()/readdir() may temporarily not return some files if there has been changes in the directory since the opendir(). That means Dovecot thinks a message is expunged, while in fact it really isn't, and the next scan would usually show it again.
Currently when that happens, Dovecot usually prints an error message about it and rebuilds indexes. Of course, in real life clients aren't often bombing the same mailbox with tons of changes in multiple connections, which is usually needed to trigger this.
I wrote a test program which tests this:
http://dovecot.org/tmp/readdir.c
I'd like to hear if you can run it in some system without errors. I tested Linux 2.4 and 2.6 with ext2, ext3, xfs and reiser3, Solaris 8/ufs and OpenBSD 3.5/sparc64. Only OpenBSD passed the test, but I'm not sure if it's only because the computer was so slow and didn't switch between processes hard enough. I'd be especially interested about FreeBSD and various NFS systems.
If it actually works properly in some systems, I guess I'll make the extra locking configurable.