[Oleg Krylov]

В ДНС сервере, отвечающем за ваш домен, должна быть запись типа PTR »

Это понятно, но здесь дело в другом. Здесь обратная проверка по MX. Т.е. сервер получателя перед приемом, выполняет подключение к серверу, которым представился отправитель и пытается выполнить тестовую отправку (на самом деле никакой отправки нет, просто ему нужен Result Code 250 Recipient OK). Абсолютно дебильная система. Во-первых, в крупных компаниях, например том же Google или нашем Mail.ru сервера отправки и получения зачастую находятся даже в разных подсетях. И серверы отправки могут даже не принимать входящие подключения. Во-вторых, Вы представьте себе ситуацию, когда пытаются обменяться почтой два таких вот "мегасекурных" сервера. Т.е. сервер такого горе-админа отправляет письмо серверу второго горе-такого-же. При посыле RCPT TO в ответ сервер-получатель пытается выполнить тестовое подключение, и естественно получит 451, т.к. образуется цикл. И два этих долб№$а будут с умным видом свысока отвечать своим пользователям: "У них админ тупой, сервер у них неправильно настроен, не по стандартам". А пользователь будет страдать. Когда наконец наше ИТ-сообщество поймет, что ИТ-персонал, такая же прислуга, как швейцары и официанты. Первичен бизнес, и его требования, ибо это приносит денег. А такие вот сверхрешения деньги могут только красть.
scrappy, что Вам посоветовать? Посмотрите в логе SMTP есть ли в этот момент попытки подключения от их серверов с отправкой от указанного в ответе пользователя. У Вас есть релеи на пути принимающие\отправляющие?