Error Enviando Correo - Connection refused; IP address - URGENTE

Hola Grupo,

Tenemos el siguiente problema: hemos contratado un servicio de hosting con
un proveedor en Estados Unidos, con el cual tenemos varias cuentas de
correo, en toda la empresa el envío y recepción de correos funciona
perfecto, menos en una sucursal, donde al intentar enviar un correo
(recibiendo sí funciona) desde outlook o outlook express el servidor genera
el siguiente error:

Connection refused; IP address "xxx.xxx.xxx.xxx" donde la dirección
corresponde a la dirección asignada por el ISP, (la conexión es por cable);
hemos hecho pruebas con otros ISP (por teléfono) y hemos notado que no
funcionan algunos de ellos, en los equipos ya hemos realizado las ultimas
actualizaciones de software, (service pack y demás), tanto de la máquina
como de Outlook, pareciera que el servidor smtp de nuestro proveedor
rechazara o bloqueara la dirección IP asignada por el ISP.

Nuestro proveedor de Hosting dice que pareciera ser problema del ISP, pero
porqué si funcionan cuentas de correo de otros dominios en ese mismo ISP.

Sí hacemos la siguiente prueba en CMD (telnet smtp.midominio.com 25)
funciona.

De antemano y como siempre Gracias


Alexander Díaz