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.
First, DON'T capitulate. He is not only an idiot but DANGEROUSLY wrong. In fact, releasing this information would violate the PCI standard (which is what I'm assuming the audit is for since it's a payment processor) along with every other standard out there and just plain common sense. It would also expose your company to all sorts of liabilities.
The next thing I would do is send an email to your boss saying he needs to get corporate counsel involved to determine the legal exposure the company would be facing by proceeding with this action.
This last bit is up to you, but I would contact VISA with this information and get his PCI auditor status pulled.
Best Answer
You could try deleting and re-creating their profile.
Also does the account the machine is logged in with match that person since those creditentials will get passed though as well.