Buenas itvquintanar
Pues lo primero que intentaría sería, por hacer pruebas, una conexión cualquiera a un servidor SMTP por telnet o por donde sea. Por ejemplo,
ncat -C gmail-smtp-in.l.google.com 25
Puedes hacerlo con telnet si quieres, o nc o la herramienta que quieras. Eso nos va a determinar en principio si es un problema concreto con un destino específico, o con cualquiera. Si conectase en el anterior ejemplo, que es el MX de gmail, ya sabríamos que el problema es específico al proveedor vuestro de correo, y la única solución es llamarles para ver que diablos pasa.
En el caso de que el ejemplo anterior también diese error de conexión, es decir, no se estableciese, miraría dos cosas principalmente. La primera, intentaría realizar exactamente lo mismo desde otro equipo diferente. La segunda, revisaría los filtros del Firewall del Router, a ver si existe alguna entrada que alguien haya añadido, incluso me plantearía resetearlo (el Router)