I am going to assume you use the Imap class and StoreMessage method to store a mail in the Inbox of an IMAP server. Is this correct?
The IMAP protocol itself doesn't distinguish between e-mail that have and have not been sent, so the message you are seeing might be produced by the e-mail client in which you see it - would it be possible to let us know where the message is actually showing?
For example, the client might add some custom header into already-sent e-mail, and in order to remove the message, you would have to do that as well.
Downloading two e-mails - one with and the other without the message - should make it possible to compare them and the difference. I needed, send us two sample e-mails for analysis to email@example.com (in a ZIP file to prevent any modifications to be done during the transfer).