A mi esto solo me ocurrió una vez... Y en mi caso la solución fué ésta (tal como la tengo guardada):
(Sacado de la web de Microsoft)
Inicie Internet Explorer, haga clic en Herramientas y, a continuación, haga clic en Opciones de Internet.
En la ficha Conexiones, haga clic en Configuración de LAN.
Haga clic para desactivar la casilla No usar servidor proxy para direcciones locales y, después, haga clic en Opciones avanzadas.
Escriba la dirección IP del servidor CAS de Exchange 2007 y haga clic en Aceptar.
Reinicie Outlook.
En cualquier caso, el error 0X8004010F es un error genérico y se puede dar por multiples causas... Si no te sirve la solución podrías empezar por mirar aquí:
http://blogs.technet.com/b/exchange/...9/3401966.aspx