Письмо отправляется порядка 13-14 секунд.
При немедленной отправке письма в логе вот что:

[15:32:03] C: Connected to smtp.mail.ru, port 25
[15:32:04] S: 220 smtp25.mail.ru ESMTP ready
[15:32:16] C: EHLO [192.168.1.183]
[15:32:16] S: 250-smtp25.mail.ru
...

Как видим после установления соединения проходит 12 секунд, после чего письмо моментально отправляется.

Компьютер Windows 7 x64 SP1, стоит антивирус Nod32, но его я пробовал полностью удалять, это ни на что не влияет.
The Bat пробовал версию и 5.2 и 4.2, режим аутентификации пробовал и открытым текстом, и защищенным каналом TLS. Всегда результат одинаковый.
Брандмауэр windows отключен.

Если пробую подключиться Telnet'ом, то сервер отвечает быстро и я быстро пишу ему EHLO, следовательно проблема в самом бате.

Может у кого есть предположения в какую сторону копать?