Outlook express y windows 2003

Entiendo que el proveedor del servicio de correo es independiente del Win2003 Server del que hablas.
No tiene nada que ver, chequea en los clientes (winXP) que la configuración dns es correcta y que la configuración de la cuenta de correo es correcta.
Por lo que cuentas, sospecho que los clientes pueden recibir correo pero no enviarlo, ¿no pueden enviar a ninguna dirección? ¿Tienen salida a internet?

Así es, es un proveedor de internet que tiene su propio servidor de correo. Si es así, ¿Mi 2003 server no tiene nada que ver verdad?
Y el temas es así, puedo mandar y recibir mails desde las PC clientes, cuando rebota los mails es cuando pongo responder directamente desde un mail que estoy leyendo.

¿Puedes enviar y recibir mails con normalidad pero si en vez de "enviar un nuevo mail" responden a uno no pueden enviarlo?
¿Pasa con todas las direcciones o con una en particular? ¿Qué error da?
La verdad es que cosa semejante nunca me había pasado.
Y contestando a tu primera pregunta, el Windows 2003 Server que tienes no tiene nada que ver con esto.
Dime que error da y si es a cualquier dirección o solo a una y a ver si lo podemos solucionar

Si quiero responder desde una cuenta de gmail a la dirección de correo que esta configurada en el outlook, me llega un mail con el siguiente contenido.
This is an automatically generated Delivery Status Notification
Delivery to the following recipient failed permanently:
    [email protected]
Technical details of permanent failure:
DNS Error: Domain name not found
  ----- Original message -----
MIME-Version: 1.0
Received: by 10.151.115.1 with SMTP id s1mr15350097ybm.106.1256751053715; Wed,
       28 Oct 2009 10:30:53 -0700 (PDT)
In-Reply-To: <149889C99816486583DA13506950B740@administracion1>
References: <149889C99816486583DA13506950B740@administracion1>
Date: Wed, 28 Oct 2009 14:30:53 -0300
Message-ID: <[email protected]>
Subject: Re: PAGO
From: Nicolas Pietrasanta <[email protected]>
To: produccion - impresa
<[email protected]>
Content-Type: multipart/alternative; boundary=
001e680f15b020bb2b04770228ee
--001e680f15b020bb2b04770228ee
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
prueba correo
El 28 de octubre de 2009 12:31, producción - impresa <
- Mostrar texto citado -

Lo que te dice el error que has puesto es que la dirección de entrega no existe, que hay un problema de dns porque no encuentra el dominio de la dirección a la que se lo envías.
Si lo que estas haciendo es responder a un mail, suponemos que la dirección existe.
Prueba a mandar un mail a esa dirección sin responder a un correo, si no creando un correo nuevo e introduciendo la dirección de la cuenta manualmente.
Según lo que me has dicho, ¿ahora el problema es al enviar desde una cuenta externa (gmail) a una cuenta interna (la que esta configurada en el Outlook) no? Si es eso, y lo haces por webmail, el mail sale por gmail y no creo que tenga un error, así que debe ser otra cosa.

Exactamente eso es lo que pasa. Si envío desde la opción "enviar correo nuevo" e ingreso la dirección el mail llega perfectamente. Desde la cuenta configurada en outlook tanto enviar correo nuevo como responder funcionan.
El único problema es cuando respondo desde la dirección de gmail.

La verdad es que lo que te ocurre es muy raro, nunca me había pasado, pero al ser un problema que se genera desde gmail, creo que lo mejor es que te pongas en contacto con ellos ya que tu no tienes posibilidad de solucionar el problema. Yo me inclino a pensar que es un problema de DNS, pero en todo caso es un problema de gmail.