MTA на Yandex Cloud: Connection timed out

На виртуальной машине в Yandex Cloud не работает отправка почты посредством sendmail на любой почтовый сервер, кроме яндекса, в журнале записываются ошибки вида:
stat=Deferred: Connection timed out with mxs.mail.ru

Проблема в том, что Яндекс Cloud автоматически блокирует трафик, который отправляется с публичных IP-адресов виртуальной машины на TCP-порт 25 любых серверов в Интернете. Исключение — соединения с почтовыми серверами Яндекс Почты.
Yandex Cloud может предоставить специальный публичный адрес с открытым 25 TCP-портом по запросу в техническую поддержку. При этом он оставляет за собой право заблокировать исходящий трафик на 25 порту, при рассылке спама.
Для уже используемых публичных IP-адресов порт 25 не открывается.