Это сообщение на стороне отправителя, а что пишет Postfix в логах на твоей стороне?

А там ничего нету... ни одного упоминания об этом домене...

У них сервер отправляет напрямую твоему серверу, или между вами есть промежуточное звено?

То есть напрямую??? traceroute к ним выглядит примерно так: CNT1-gi-3-2.cnt.ru (212.15.122.3) 8.166 ms 3.957 ms 4.085 ms 4 msk-dsr5-ge1-39.rt-comm.ru (195.161.2.69) 4.471 ms 4.120 ms 4.157 ms 5 sl-gw11-lon-4-0-2.sprintlink.net (82.195.190.193) 59.028 ms * 58.335 ms 6 sl-bb20-lon-11-0.sprintlink.net (213.206.128.56) 61.318 ms 59.178 ms 58.407 ms 7 sl-bb21-par-14-0.sprintlink.net (213.206.129.70) 65.841 ms 65.302 ms 68.245 ms 8 sl-bb20-fra-4-0.sprintlink.net (213.206.129.148) 68.477 ms 64.567 ms 64.053 ms 9 sl-gw11-fra-5-0.sprintlink.net (217.147.96.69) 64.737 ms 64.535 ms 64.735 ms 10 peer-sprint-l.newline.net.ua (80.91.180.5) 110.327 ms 110.874 ms 110.353 ms 11 KE2-KT1.rtr.newline.net.ua (80.91.160.158) 110.888 ms 110.893 ms 111.589 ms 12 nexus-rgw.newline.net.ua (80.91.173.146) 117.320 ms 117.808 ms 118.230 ms

Читать уже не учат?

>I wasn't able to establish an SMTP connection.

Как пить дать фильтр рубит, или порт не слушается.

напрямую - это значит, что у вас с обеих сторон стоят полноценные почтовые сервера, которые принимают и отправляют почту самостоятельно, а не через почтовые сервера провайдеров, тогда в логах обязательно будет запись о том, что происходит. Выполняешь:

tail -f /var/log/syslog

звонишь или по ICQ просишь отправить письмо и смотришь в реальном времени записи в логах.

напрямую

тогда выполни

tail -f /var/log/syslog

звонишь или по ICQ просишь отправить письмо и смотришь в реальном времени записи в логах. Смотри запись по IP адресу их сервера (который надо знать на этом этапе). Тогда и узнаешь, почему твой почтовик не принимает от них почту.

сенкс... да я понял уже :-). Два раза не надо :-)

пускай на твой сервер telnet-ом встанут на 25 порт, и ты попробуй.