Хитрая проблема с почтой

Уже второй раз за полгода сталкиваемся с очень непонятной штукой.

Есть почтовый сервер, postfix + dovecot, все дела, данные о логинах в постгресе, несколько разных доменов, всё настроено, всё работает уже не первый год. Ну, почти работает. Внезапно, в определённый момент, письма перестают уходить. Выглядит это так: постфикс соединяется с удалённым сервером (гугл, яндекс, whatever), и... ничего. Висит пока не отваливается с руганью timed out while receiving the initial server greeting.

Сначала казалось, что это кто-то из юзеров начал слать спам (такое было), и сервер попал в какой-нибудь блэклист. Но потом оказалось, что спама никто особо не слал, да и самое интересное - телнет на 25-й порт этих серверов не выдаёт даже классического почтового приветствия (ну там 220 pornoporno.ru ESMTP Exim 4.69 Thu, 12 Sep 2013 11:48:27 +0400 GTFO). Вообще не выдаёт ничего, висит, как будто Великий Фаерволл жрёт пакеты.

Более того, под рукой есть ещё пара серверов, на которых точно не настроены никакие блэклисты, в принципе. С ними этот проблемный сервер также не соединяется. При этом в остальном всё ок, вся почта принимается, между локальными доменами ходит, сайты открываются, ssh на месте - в общем, всё свидетельствует о нормальном интернете. Просмотр tcpdump ничего ценного не выдал - увы, я в этом плохо понимаю, но на вид пакеты сначала идут, а потом не идут.

Всё выглядит так, как будто у хостера на роутере проблемы именно с исходящим 25-м портом.

Во время первой такой проблемы мы, естественно, написали в поддержку, на что они нам ответили, что никаких проблем нет. Ну, то есть они не нашли. Через какое-то время, в процессе неторопливой ругани с поддержкой, всё ожило само. А вот сегодня опять произошло, и опять поддержка ничего не видит (хотя в этот раз у нас есть определённые подозрения на этот счёт).

Кто подскажет, что я мог упустить, и в чём может быть проблема?