Since your "Domain Admins" can access their mailboxes without problems this doesn't point to a database mounting problem. Has somebody been playing around with permissions in the Active Directory? Start by querying everybody who would have access to do such a thing (Enterprise Admins, Domain Admins).
Are you seeing anything amiss in the event logs on the Exchange Server computer? That is the absolute first place to look.
Perhaps an obvious question, since you say it was working y'day, but: The client computers are joined to the domain and the users are logging-on with domain accounts and not local accounts-- correct?
I'd examine the default permissions on the Exchange organization by turning on the "Security" tab in Exchange System Manager (create a REG_DWORD value called "ShowSecurityPage" in the key "HKEY_CURRENT_USER\Software\Microsoft\Exchange\ExAdmin").
I'm having a really hard time finding a doc from Microsoft that describes the default top-of-the-organization permissions for Exchange 2003! It would probably be easiest if you dumped a copy of the ACL using the DSACLS command and added that as an edit to your question.
To formulate the command-line for the DSACLS command you're going to need to know the distinguished name of your Exchange organiation. The easiest way to do this is to install the "Windows Support Tools" from the W2K3 CD, in the "SUPPORT" folder. After you've got that installed, start "ADSIEDIT.MSC" from Start / Run.
Expand the "Configuration" container in the left pane, the "CN=Configuration,..." sub-node, the "CN=Services" container, and the "CN=Microsoft Exchange". In that "CN=Microsoft Exchange" container you'll find your Exchange organization as a "CN=Organization Name Here" node.
Bring up the properties for your organization, scroll down to the "distinguisedName" attribute, highlight it and click "Edit", and copy the contents of the "Value" text-box (making no changes!).
Close up ADSIEDIT. Click Start / Run and enter the following command, pasting in the "distinuguiedName" value you copied inside the double-quotation marks (leaving the double-quotation marks in the command):
CMD /C DSACLS "paste distinguishedName value here" > %TEMP%\ACL.TXT
A window will briefly appear and close. Click Start / Run and enter the command:
%TEMP%\ACL.TXT
This will bring up your top-level Exchange organiation permissions in a Notepad window.
I bumped into this (old) question while looking for something else, but I will add an answer for anyone that ends up here actually looking for an answer...
An option you can use (assuming you have a least a 2008 level AD domain) is to apply a password policy with your required "lighter" settings specifically against the server(s) you have hosting ADLDS. While 2003 and below had only domain-wide password policy settings, 2008 and up can support fine-grained password policies configured against certain areas of the domain.
Best Answer
No, here's what's happening:
Outlook caches the users credentials in Credential Manager and fires them off every time it needs to grab something from 365/Exchange. When the user changes their domain password that get's replicated to 365/Exchange, however, Outlooks credentials remain out of date. The the user attempts to connect, they get an unauthorized response, and then prompted to update their credentials in Outlook.
This, I'm afraid, is unavoidable.
As an aside, there is a bug with Outlook 2010/13 where it won't remember the credentials at all after they've been reentered, and thus prompt every time Outlook opens, there's also a fix for that.