Exchange 2003 - Admins Cannot Create Contacts in ESM

Error: An Exchange server cannot be found in the domain.

I've been looking into this for the better part of a week in an attempt to try to understand what is happening here.  We know that we can't recreate the error/issue (we're in another location from the admins that are experiencing this error).  I created a test account in the admins OU and matched it exactly to one of admins' account, I had no issue.  I looked at the GPOs being enforced to that specific OU and there is no difference between that OU to any other admins OU.  I looked at the explicit permissions for the "Contacts" OU, these are set correctly.  

I even went as far to get the admin to check which domain controller he's authenticating to with his admin account to ensure that was correct.  I also checked the event logs on each DC and could not find any warnings/errors normally associated with this type of issue, for the exception of event ID 1988 (this event is typical of our environment); that would suggest there to be a problem.  All looks normal.

Can someone offer any guidance?