Here you go, maildir syncing problems finally fixed (I hope). Well, except there's this "new-dir-only syncing" optimization which I'm not really sure if it works as it should.
The bug really was in index code as I was beginning to suspect. The good thing is that while trying to figure it out over the last several weeks I thought of many other potential problems (race conditions) which got fixed. Those would have been much harder to find than this one :)
Finally I thought I'd stop looking at the code and just begin dumping tons of debugging data to see where exactly it goes wrong. After few hours of debugging I figured out it was because message was being removed from index but not from maildir. 5 hours of sleep later I woke up, thought a while, figured out where it must be, got up, half an hour more debugging and found it. :) Code merging two UID range buffers into one was buggy, inserting one line of code fixed it.
So .. Maybe I'll finally start using this myself now. The next important problems seem to be some random error messages about index locking timeouts and some asserts in some situations.