Do you use IMAP push?
1.3.8 had a bug where sometimes it could get messages over push from a different folder.
1.4 has this fixed, please try updating.
If you don't use push, or the 1.4 doesn't help, it may be an IMAP server issue (web mail is different), and I'd like to see a debug log. Thanks.