[monkkey]

1. Возможно, не на все DNS еще реплицированы записи о Вашем почтовике.
2.

Received: from [77.77.77.77] by win.mail.ru with HTTP »

- из DNS
3. К Вашему серверу, допустим, телнетом можно снаружи приконнектиться по IP или имени на 25 порт?