Telnet por el puerto 25

Si puedes acceder desde el Linux al Windows, y desde el propio Linux a si mismo, la única opción que explique el comportamiento que describes es que tengas un firewall en el camino que se este comiendo los paquetes.
Si en el Linux no has encontrado nada en el firewall con iptabes o ipchains (léete los manuales por si acaso estas filtrando algo y no lo has visto) quizá estés filtrando esos paquetes en el firewall del Windows XP (que se llama directivas de seguridad IP o algo así)
Siento no poderte ayudar más, pero tampoco dispongo de mucha más información.

Solamente necesitas tener bien configurado el postfix y asegurarte que no tienes ningún firewall instalado en el servidor.
Prueba desde el propio servidor a hacer:
Telnet localhost 25
Si esto no funciona significa que no esta el postfix escuchando en ese puerto.
Si por el contrario te funciona puede significar que tengas un firewall filtrando las conexiones desde el exterior. Prueba con
ipchains -L
O
iptables -L
Si te encuentras con entradas como DROP, DENY o REJECT que afecten al puerto 25 las puedes eliminar con:
Iptables -D INPUT x
Ipchains -D INPUT x
Donde INPUT corresponde a la chain correspondiente y x corresponde al numero de linea de esa chain
Salu2 y suerte

El telnet desde el propio equipo resulto super bien y con el iptables -L no vi nada que tuviera relación con el puerto 25.

OK ..
Ya más o menos tengo la misma estructura de servicios de correo. Lo primero es que el gateway de mi servidor de correo ( sendmail ) es el IP del equipo con el antivirus engine.
Lo segundo es que quizás en este equipo tienes algo de IPTABLES activo que está bloqueando el 25 ..¿?
Será que el 25 está ocupado respondiendo a una aplicación en especial y por eso es que no te responde ..
Si puedes pásame un view de lo que recibes cuando tratas de hacerte telnet al 25 en tu servidor de correo para ver que mensaje te está arrojando.
salud .. !

Lo primero, aunque parezca obvio, es asegurarte que en linux tienes habilitado telnet.
En la máquina Linux, ejecuta "telnet localhost" o "telnet 127.0.0.1" para verificar que efectivamente funciona (en los linux actuales está deshabilitado).
El siguiente paso es asegurarte que tienes telnet en tu máquina.
Tercer paso: si tienes service pack 2 instalado en tu máquina windows, deshabilítalo temporalmente: a lo mejor te está bloqueando el acceso.
Cuarto paso: haz una prueba desde la máquina cliente en estas condiciones; si no funciona, quizá el problema se deba a condiciones de la red (existencia de firewalls o filtros de paquetes entre las dos máquinas).