Сеть ни при чем. Отправил (по первой записи MX) тестовое письмо. Смотрите логи почтовика (в личку написал подробности)
UPD: Прошу прощения за тупой вопрос, но: Вы точно на нужном сервере смотрите логи и ждете письма? У Вас в DNS запись MX и запись A домена не совпадают.
UPD1: (порывшись еще) На 90% Ваша проблема - в записи MX домена. Она показывает не туда, где Вы ждете писем.
Уже разобрался! Еще раз огромное Вам спасибо за подсказку!
Да, смотрю на нужном сервере, он один. Больше негде
А то, что проблема в записи MX домена, то уже понятно на 1000 %