2 problemas con servidor smtp y usuario movil

[linux]

Holas:

Tenemos un servidor fedora core encargado del trabajo de web y correo,
usando sendmail con dovecot y auth. En los clientes outlook, se configuran
las cuentas con autenticación para smtp usando las mismas credenciales que
el correo pop. El proveedor de servicios es entel.

Problema_1: Es con un usuario movil que puede funcionar correctamente desde
faena y desde la mayoria de las partes externas a la red del trabajo. Este
usuario a veces debe visitar empresas tanto en Chile como en el extranjero y
al conectarse a internet para ver su correo, en algunas partes obtiene el
mensaje “Se ha encontrado el servidor especificado pero no hay respuesta.
Compruebe que el puerto y la información SSL son correctos” al intentar
_enviar_ correo. La recepcion ocurre sin problemas.

El servidor de correo es entrante y saliente son el mismo.


El segundo problema es con el gerente general   :( 
Es similar al caso anterior, solo que el problema es desde su casa en
santiago, y el mensaje es "Outlook no puede conectar con el servidor de
correo saliente (SMTP)". Del mismo modo que antes, se puede recibir correo
sin problemas.

Los demas usuarios moviles no han tenido problemas.

Siguendole la pista al codigo de error de outlook, me encontre con que
Telmex bloquea (al menos en Mexico) el puerto 25 y por eso no se podria
enviar correo desde una conexión asociada a ellos.

Alguna pista?