I had this happen to me last night on my 8130. I had 4 separate messages that I deleted from Outlook (hard delete) and they still showed on my 8130. Even tried running a manual reconciliation with no luck. This has not happened previously and I've not had any other BB users complain about this.
Our BES is on a separate server. Will check the mai32.dll versions on Exchange and BES.