[Sadok]

Т.е. не проходит "HELO"

Т.е. не проходит "EHLO". Это команда ESMTP, хотя с mail.ru ESMTP-сессии у меня ходят нормально. Мысль другая: не настроена/включена SMTP-авторизация (на mail.ru она нужна). Читать здесь