Definitely odd. When I have POP issues, I manually telnet into the POP server and look around:
telnet mail.mydomain.com 110
LIST (this will list message IDs)
RETR XX (display message #XX)
DELE XX (delete message #XX)
Your POP client is supposed to DELE messages, according to the "Remove" setting. Telnetting into the server will show if this is happening. If it really is happening, and the message is reappearing on the server, then you'll have to let Support know.
I like IMAP, but if there's a server issue, I don't know if that'll fix it.