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.