Traveler must think those messages are in your Inbox. So, why would Traveler think that?
I assume when you look at Notes on your PC that you do not see the deleted items. If you are using mail replicas, I assume the replica and the mail database on the server show the same thing.
Make sure your mail template is a supported one. Anything later then 7.0.2 would be supported.
Have you upgraded your mail template recently? If so, from what to what?
Do you have more than one “Inbox”?
Are all users experiencing this problem or just one?
If those things do not lead you to a solution, we’ll need to see a user dump “tell traveler dump ” and some logs (FINEST level) for that user. For us to get the logs, you would need to open a PMR.