Dikenson на майл ру можно смотреть хидеры! желтеньая кнопа с написью rfc  - там где ответить переслать  и тд !  
 1 - Сходи на 
www.dsnreport.com и проверь свой почтовый домен.  там тоже ругается, что твой ip адрес  77.242.160.42  не является публичным !  
 Error: At least one of your MX records points to an IP address that is not a public IP. The problem IP(s) are: 
 77.242.160.42 is not a public IP 
 Note that these IPs are not reachable, which can cause extra resource usage, slight mail delays, and possibly bounced mail. 
  Что и это почему - я хз .  
 2 -  нет SPF записи  
 3 - строка приглаешения  greeting  тоже проблемная ! 
 WARNING: One or more of your mailservers is claiming to be a host other than what it really is (the SMTP greeting should be a 3-digit code, followed by a space or a dash, then the host name). If your mailserver sends out E-mail using this domain in its EHLO or HELO, your E-mail might get blocked by anti-spam software. This is also a technical violation of RFC821 4.3 (and RFC2821 4.3.1). Note that the hostname given in the SMTP greeting should have an A record pointing back to the same server. Note that this one test may use a cached DNS record.   
 mx.herbs.kiev.ua claims to be non-existent host herbs.kiev.ua: 
 220-herbs.kiev.ua ESMTP MDaemon 8.1.3; Fri, 18 May 2007 18:25:22 +0300 220-Unauthorized relay prohibited. 220 All transactions and IP addresses are logged.    
 Имхо вот тут и зарыта собака ! По идее если ты сказал что я 220-herbs.kiev.ua 
 то в днс  должна быть запись с типом А на такое имя - herbs.kiev.ua ! А ее нет !    
 4 - telnet 77.242.160.42 25  
 Ответ:  
 501 Domain must resolve 
 Connection to host lost.   
 как это понимать ? Такого никак не должно быть ! Думайте сэр !