Parte II: ID 9562: Failed to read attribute msExchUserAccountControl from Active Directory...
Bueno el problema persistió. Pero ya descrubí el verdadero problema, pero para llegar a la solución voy a indicar un escenario inicial.
Cuando instalas Windows Server 2003 + SP1 y posteriormente tratas de instalar Exchange 2003, Windows Server presenta una advertencia de que Exchange 2003 no es compatible a menos de que se instale un parche (no recuerdo cual), sin embargo esto hace referencia al SP2 de Exchange.
Ahora resulta que cuando instalas primero Windows Server 2003, sin SP1, e instalas Exchange 2003 no existe ningun problema. Al actualizar Windows Server 2003 con SP1 sin instalar el SP2 de Exchange, este deja de funcionar correctamente y es ahí cuando se presenta el error.
En resumen, si tienes un servidor con Windows Server 2003 Exchange 2003 y los quieres actualizar con el último SP de ambos productos, primero instala el SP1 de Windows y luego el SP2 de Exchange para evitar un mal funcionamiento.