É seguro assumir que isso é o Exchange 2003 e você está acessando o Exchange usando o Outlook? Apenas para esclarecimentos, esta é uma estação de trabalho que se une ao domínio, e você está tentando isso com um usuário do AD e com um usuário local? Quando você está usando o usuário local e diz que está funcionando, você está solicitando credenciais de domínio e inserindo a conta do AD (domínio \ nome de usuário)? Esta é a mesma conta que depois você faz logon na estação de trabalho como quando não conecta? Quando você não consegue se conectar, você está recebendo algum tipo de mensagem de erro?
Obrigado Paul