This post has updates. See at the end of the post
I noticed yesterday that I couldn't search for some email that I knew existed. On closer inspection I found a huge chunk of my archive inbox to be missing. Several months worth of emails, they stopped in March and then continued with the emails from yesterday that I had copied in from my Inbox.
The same happened to my fedora-devel and xorg-devel folders, possibly others. Re-running offlineimap to sync these pulled down hundreds of emails, so I let it run overnight. This morning I discovered that sometimes offlineimap simply states something like "Deleted 1018 messages" and they're gone again. This is cumulative, it seems to delete only newer ones (I was at September 2010, but after one more run I'm now back to July 2010 being the newest messages in in my xorg-devel folder).
The good news is that the emails are still on the server. Also, so far only mailboxes with huge numbers of emails (>10000) seem to be affected, smaller mailboxes appear to work fine.
Update May 30: Filed as Bug 708898
Update May 30
I downgraded to offlineimap 6.2.0 which is in F14 (offlineimap-6.2.0-2.fc14.noarch) and managed to eventually resync my mailboxes. Then I went back to F15's offlineimap-6.3.3-1.fc15.noarch. Of course it didn't trigger on my test mailbox, but it did then do the same thing again on my xorg-devel inbox.
Syncing lists-xorg: IMAP -> Maildir
Deleting 8181 messages (33540, 335
F15's offlineimap-6.2.0-3.fc15.noarch does not show this behaviour and seems to resync the locally deleted emails. Of course that'll take a while, but I'll try to get logs this time (my first couple of tries to get logs from offlineimap crashed it).