On my Strato V-Server I host mail servers for various domains using postfix on Plesk 12.5. Recently I found that mails that are sent through this mail server to addresses of GMX and Web.de will not arrive, starting around December 2015. Instead, they are returned to the sender, stating the following i.e.: Of course, there is a PTR record set in the DNS-Settings of Plesk. Within the list of any domain-specific DNS zone, is an entry like this: This is taken from the default DNS template, whose PTR template certainly looks like this: To me it looks alright, but GMX/Web.de is still blocking out mails from all addresses of all domains hosted in this Plesk environment. So what is the problem here? What do I need to change to get this working again?