POP! ooo - nostalgia.
Make sure that the setting for "remove copy from server after retrieving" is set. If it is, and the mails come back, then it's most likely the POP3 server isn't honouring the delete. Some providers flag a mail as deleted (and clear them out at a later time) rather than immediately send them to the bin; I'm not sure how well Apple Mail copes with those.