Is it safe to assume that this is Exchange 2003, and you're accessing Exchange using Outlook? Just for some clarification, this is a workstation that is joined to the domain, and you're trying this with an AD user and with a local user? When you're using the local user, and you say it is working, are you being prompted for domain credentials and entering the AD account (domain\user name)? Is this the same account that you later log on to the workstation as when it does not connect? When you are unable to connect, are you getting any kind of error message?
Thanks,
Paul