Linux - Postfix - puerto 25 cerrado

Hola gracias a todos por la ayuda que me puedan brindar.
Les comento mi problema:

Tengo instalado un servidor de correo (Postfix), en cuanto a la configuración,
creo que no hay ningun problema con la misma ya que es una copia exacta (obviamente con
las modificaciones pertinentes) de otra configuración que me paso un amigo y que funciona
muy bien. La situación que se me presenta es la siguiente:
-Puedo eviar correos a cuentas externas(hotmail, yahoo, etc...) pero los que me envían
desde allí, son rechazados en sus respectivos servidores de correo.
-Hay algo que bloquea el puerto 25, porque no se puede hacer un telnet al mismo desde
una maquina remota.
- No tengo firewall, la distribución es un Red Hat 8, hay a una serie de filtros en
iptables que no bloquean el puerto 25 y aun asi no funcionaba. Quite esos filtros
de iptables por las dudas y aún así no funciona. Estoy hablando del problema
del bloqueo al puerto 25.

¿Qué otra cosa puedo probar para que funcione?
¿Qué es lo que puede estar volviendome loco?!!!!!!!