If you hadn't said that you have deleted the message from the server I would have proposed that Pegasus Mail never records a successful download so it comes down again on the next POP3 cycle. 

At this point I would want to determine whether the issue is with deletion on the server or at the local

level.  To do this, the next time you delete the message record the .cnm filename. 

When the message appears again check its .cnm

filename.  A different filename indicates the message came down again.

It wouldn't hurt to do a system restart immediately after the next delete to clean out any cobwebs that might be affecting this.

BTW, when you delete the message from within Pegasus Mail does it disappear from the new mail folder and appear in the deleted messages folder (assuming deleted messages are being preserved until Pegasus Mail closes)?

I have the following problem:

A mail, dated November 25, 2016, which I have deleted several times since then always re-appears whenever I check for new mails. Sometimes even automatically.

I have also deleted this mail (xxx.cnm) in the new mail directory. But it re-appears. 

The mail has also been deleted in my POP3 account and is not visible there any more.

 Maybe, it is important that the mail has several big attachments  -  7 MB in total. 

What can I do? 

You state you have deleted the .cnm file and you have deleted it from your pop3 server host? Have you used a browser to log in to your mail provider's portal and then deleted it?