I have a couple of email accounts setup and experience the same issue. I've had this issue even with the setting to delete mail on server when I delete mail on the phone.
The accounts in question are Hotmail pop. My Exchange ActiveSync account and Gmail accounts work fine however.
One thing I've noticed is that at times the POP account will fail to connect to the server. There is no rhyme or reason. I'm guessing this is what happens when you delete the previous emails on your phone. It deletes them locally but fails to tell your email server so the next time it connects to download mail it simply downloads the same mail all over again.
I think it's one of the last options you select when your setting up your hotmail accnt. Manualy. I printed out a fairly sucessful ver. If you want them let me know. I still log into Widows Live mail most of the time anyways.