I had that from time to time also. I found that, until you delete the messages from the server (as in open them your email app on your PC) they will continue. What I did was to simply forward all my pop accounts (personal and business) to my gmail account. Aside from taking care of the problem, I also get instant push email on all my accounts, through gmail.
I want to send my pop3 emails to my Gmail account. Do I have to set something in the pop3 account or the Gmail account?
Go into gmail on the web. Click on "settings" on the upper right. Go to "accounts and import". Under the section "check mail using pop" click on the button "add pop3 account". Follow the prompts. (Personally, I recommend "leave a copy of received mail on server", and "label incoming messages" with a label that identifies the messages as coming from that account, to make it easier to filter messages from a particular account.)
This has happened to me, and I *think* I solved the problem without forwarding to gmail, etc.
First, I don't delete from the server from my Droid, only from the device. When I receive a POP3 email I let it sit in the inbox for a couple of hours before deleting. It may be my imagination, but immediately deleting an email when I first open it seems to make it more likely that it will return to my inbox. I delete emails from the server from my PC on a regular basis.
Since I started doing this, I haven't had the problem of deleted emails reappearing.
One of the major reasons that I use gmail as a hub for all of my mail accounts is that gmail's spam catcher is absolutely excellent. My ISP's mail server does not filter at all, and over 75% of the mail that we get at that account is junk. Using gmail on a mobile device makes it far more likely that when I get an email notification on my phone, it is an email that I at least care about seeing the subject line.