Я не знаю что это за провайдер... Если какая-то домашняя сеть, то конечно, 25 порт может быть зафильтрован у вышестоящего провайдера.
Кстати, не обязательно на файрволе маршрутизатора резать. Можно, например, на коммутаторах создать подобный ACL (если функционал коммутатора поддерживает)...
Напрягай техподдержку прова, пусть проверяют более детально. Посоветуй им запустить сниффер и пускай проверяют, проходят ли твои запросы по 25 порту через из оборудование к вышестоящему провайдеру...