Каким почтовиком пользуетесь?
Хотелось бы, чтобы вы выставили уровень логирования до максимального и логи выложили сюда. С обоих серверов.
Также, проверьте маршрутизацию. Данные о DNS обоих серверов наверняка лежат в таблице на вашем DNS-сервере. А вот почтовые сервера могут находится в разных VLAN и не иметь доступа друг-к-другу.
Также, попробуйте сделать: nslookup -type=mx <другой_почтовый_сервер> и выложить результат сюда, вместе с логами.
Также может потребоваться подробное описание конфига вашей сети в части этих серверов, DNS, маршрутизаторов, свитчей. Включая конфиги этого железа (на словах достаточно) с ВЛАНами, Транками и прочим.
В общем, нужны подробности.
