Same issue here.
Just upgraded from 6.0 to 6.0.4. I'm having this exact same issue, and yeah, it has most of our users fuming. It seems as though it's caused mostly by those moving a message that was stored locally (either via intentional archiving, or by the mail client app storing a new message in Drafts, locally, during composition) up to the server via IMAP. Messages being moved from one IMAP folder to another IMAP folder seem to be OK.
mark daniel | actc
zcs 6 ose | mac pro | mac os x server 10.4.11