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.
Best Answer
Check to see if the clients are configured to use Outlook Anywhere
If they're connection via Outlook Anywhere it will always ask for credentials. You can run a
netstat -n to see if you have any 443 connections to your CAS server as well.