No, I have the same problem, it is not mail that is sent to the "Deleted Items" folder, but the ones that the rules are told to permantently delete.

I find the only way to kill the tray icon, is to close and reopen Outlook, I hope as well that there is a better way.

Mike