Exchange 2003 w/ Blackberry – Deleted Items Reappearing

Interesting situation. We have several users running Outlook 2003/2007 running in cached mode on Exchange 2003 with BES 4.1. These users will delete mail or move it to a PST from their inbox and the next day when they sign back into outlook the see the same messages reappear in their inbox. Any help would be much appreciated!!