Are you using a BIS or BES connection?
My BIS never did it correctly when I had it for my POP3 account.
If you have a BES connection, make sure your Messages -> Options -> Email Reconciliation -> Delete On option is set to Mailbox & Handheld or Prompt.
|