For some reason, all users on our LAN and via virtual private network (VPN) cannot authenticate to Outlook if they log on using their local account on their PCs. Every time they start Outlook and enter their ID, password and domain, it tells users they are using incorrect user IDs and passwords. When they log on using their domain accounts, they can access Outlook fine. We rebooted the Exchange server, and, for a short time, it worked fine. But after a few days, it stopped responding. We recently had two backup domain controllers (BDC) on our LAN and downgraded one NT4 BDC into a Win2k member server. Any suggestions?
This sounds like it is working as it should be. In order to access an Exchange mailbox, you need to use a domain account. An account that is in a local machine's accounts database cannot be used because it can't authenticate against your domain.
You didn't say what version of Outlook you are using; however, I suspect your version is configured to use NT Password Authentication. When you use this, Outlook will use the cached credentials that you used when logging onto the workstation for Windows NT domain access. So, if you have logged into the domain before launching Outlook, it will use the domain credentials. If you have not logged into the domain with your domain account, Outlook will prompt you for your domain credentials. If you provide those credentials and it fails, you might need to enable auditing and examine the security logs to see why it is failing. You might also try specifying the credentials in the form of domainusername to see if that logs you on.