Problemas para conectar con servidor Exchange

Buenas.

Tengo varios equipos en red que, con Outlook 2003, conectan sin problemas
con un servidor exchange que está en la intranet. De ahí comparten
contactos, tareas, correo interno...

Sin embargo hay un equipo en concreto que no consigo que conecte con el
servidor. Cuando lo intento me dice:

"La conexión a Microsoft Exchange no se encuentra disponible. Outlook
tiene que estar en linea o conectado para realizar esta acción."

¿A alguien se le ocurre dónde puede estar el error? Por lo demás el equipo
trabaja en red sin problemas, por lo que lo único que se me ocurre es que
haya algún problema con outlook.

Gracias.