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.
ad1) Please be more specific with sync issues. Do messages disappear? Do messages get duplicated?...
ad2) The basic issue is that Outlook 2003 support UDP and polling notifications. Exchange 2007 supports UDP, polling and Async notifications. Exchange 2010 only supports polling and Async notifications. This means when Outlook 2003 move from Exchange 2007 to Exchange 2010, Outlook clients will fall back to polling which by default only gets notifications every 30secs-1min. This means any change won’t show up immediately.
UDP notification support was removed from Exchange 2010. As a result, Outlook 2003 can only use polling notifications in online mode, which are still supported by RPC Client Access. This will result in a slight delay in updates to item status (30 seconds on average up to a 1 minute delay) when changes are made to items in a mailbox accessed by Outlook 2003.
source: http://social.technet.microsoft.com/Forums/en/exchange2010/thread/d5a610d5-b3cd-40a5-8653-634f3b174f4e
Best Answer
We have run into this issue with users who have clicked the "remember this password" checkbox and then changed their passwords later.
On Windows 7 check the following to see if this fixes the issue:
Control Panel/User Accounts/Manage your CredentialsMake sure no windows credentials are saved there that are referencing your email (or sharepoint) servers.