Postfix: «No route to host»

Адрес пингуется, но telnet 25 не проходит, та же ошибка. Проверил другие адреса, все нормально.

Проблема явно не на Вашей стороне. Так что решить ее Вам вряд ли удастся.

Подозреваю что у них что-то может быть заблокировано.

Может, заблокировано, а может стоят всякие перенаправления портов в локальную сеть, которые периодически отваливаются.

Самое интересное что с утра письма уходят, после обеда начинается эта ошибка.

Самое разумное в этой ситуации задать соответствующие вопросы админу данного сервера. Либо напрямую (postmaster@адрес.ru), либо через пользователей, с которыми Вы переписываетесь.

Плюнь. Проблема на стороне клиента. Пускай админ кривого почтовика сам думает. И не НАДО его в белые списки включать. КоЗла нужно наказывать!