Что делать?
1. Прописать обратную DNS зону - запись PTR. Обычно это делается в панели хостера, который предоставляет сервер или VPS.
2. Прописать в ДНС запись SPF, вида:
@ TXT v=spf1 ip4:95.167.111.222 ip6:fe00::0000:8a85:3a37:9d52 ~all
Здесь - 95.167.111.222 - это адрес с которого будут отправляться письма.
Если почта сервера обрабатывается с помощью сервиса mail.ru почта для домена, то строка будет такой: