>В зоне mydomain.com присутствуют лишь mx
>и ns записи. Почта иногда
>возвращается с ошибкой "451 Sender
>domain must resolve".

Была такая же проблема, решилась тем что заставили тех чьи IP адреса были прописать резолв на меня, а было так:
при запросе резолва по IP отвечал xxx.yyy.ru, а почту отправлял yyy.zzz.net, после того как они в зоне поменяли запись все заработало нормально

>Действительно ли
>необходимо перенастроить зону, или у
>админов, с почтовых серверов которых
>приходят откаты, параноя по поводу
>спама?