Если не боитесь
- киньте в личку свой почтовый адрес, проверю и расскажу что именно не так (если найду). Если все нормально снаружи - будем дальше копать.
UPD:
1 - те же логи: /var/log/mail.log
2 - при отправке снаружи если что-то не так, письмо возвращается отправителю с пояснением, что именно произошло.
3 - телнетом виден на каждом шаге общения по протоколу SMTP ответ от Вашего сервера
4 - "тут" проверяется только записи домена, но не MX (насколько я успел понять).
Пользователь решил продолжить мысль 17 Мая 2011, 12:19:56:
Первый же этап
vladimir@vladimir:~$ host xxx.org
xxx.org has address A.B.C.D
xxx.org mail is handled by 10 MAIL.xxx.org.
vladimir@vladimir:~$ ping mail.xxx.org
ping: unknown host mail.xxx.org
(домен и IP-адрес скрыты). И как Вы хотите, чтобы Вам доставлялись письма?