Investigating this issue required me to use a bit of Active Directory know how, as well as some Exchange-2010-Management-Shell-fu.
The first thing I checked is if my 2 domain controllers are replicating properly. My initial thought was when I updated the Hide from Exchange address lists checkbox in Active Directory Users and Computers that I had changed this on one Domain Controller, which was not replicating to the other Domain Controller that the Offline Address Book generation process happened to pick. As it turns out, the Domain Controllers are replicating properly and this is not the issue.
The next thing to do is to check out some Active Directory attributes and their current values. My preferred tool for doing low level things with Active Directory is ADExplorer from Sysinternals, however ADSI Edit will do an equally good job if you prefer that.
The first attribute I looked at on the user is the msExchHideFromAddressLists attribute. This should be FALSE if the user should appear in address lists and TRUE if they shouldn't. This is really just a sense check as it's what Active Directory Users and Computers updates when you (un)tick the Hide from Exchange address lists checkbox. This was correctly showing TRUE.
The next attribute to check is showInAddressBook. This is a multi value attribute that contains all address lists that this user should appear in. Ordinarily, this should contain at least one address list the user should appear in, but for anybody who has the msExchHideFromAddressLists attribute set to TRUE this attribute should not be set at all. This was the biggest clue, as this user still had values in this attribute which should have been removed when the Hide from Exchange address lists checkbox was checked.
The Recipient Update Service on the Exchange 2003 server is responsible for updating the value of the showInAddressBook attribute (among others) in Active Directory so I determined that for some reason the Recipient Update Service was malfunctioning here.
When I initially installed Exchange 2010, I had to run setup.com /PrepareLegacyExchangePermissions to grant the Recipient Update Service some permissions it needs because Exchange 2010 moves things around a little bit.
To check out the permissions, I opened up Active Directory Users and Computers and selected View => Advanced Features to enable me to view the security attributes for the user account in Active Directory. I then opened the offending user and checked on the security tab, and compared this to another user who should be included in the Offline Address Book. While I didn't check each permission, it was immediately obvious that the user who should be in the Offline Address Book had many more permissions granted than the user who had just left. Checking a few other users, they also had many more permissions granted than the offending user did.
Something I happened to notice purely by chance is that the offending user was not inheriting permissions from parent objects, whereas all the other users I checked were. I know from experience that this usually only happens when the user is (or once was) a member of an Active Directory privileged group. After verifying they are no longer a member of a privileged group, I went back to ADExplorer and changed the adminCount attribute on this user to 0 from 1. I then went back into Active Directory Users and Computers and enabled this user profile to inherit permissions from parent objects.
After I did that, I went into the users properties and unchecked the Hide from Exchange address lists checkbox and then checked it again. I waited a few minutes for the Recipient Update Service to do its thing, and sure enough 5 minutes later when I looked at the user object in ADExplorer the Recipient Update Service had removed the showInAddressBook attributes that it had no permission to do earlier. A quick manual rebuild of the Offline Address Book and everybody is happy.
Finally tracked down the cause. Our Cisco ASA firewall was to blame.
From http://jamesosw.wordpress.com/2009/12/30/exchange-hub-transport-unable-to-communicate-at-different-active-directory-sites/:
If you happen to be deploying Exchange 2007/Exchange 2010 Server in a
multiple sites environment and using a Cisco ASA Firewall as your VPN
tunnel, you’ll likely encounter issues below:
Users are only able to send emails within the same Active
Directory site
When users attempt to send an email over to the next hop/Active
Directory Site, under the Exchange Queue, you’ll see a Retry status:
451 4.4.0 Primary target IP address responded with “451 5.7.3 Cannot
achieve Exchange Server authentication” SMTPRelay to remote AD Site
When you attempt to telnet from the Exchange Servers from both
site, you’ll get such response from the telnet command:
220*************
The only way to fix this is to use the Commandline Interface (CLI) and
type in this command:
telnet YourCiscoManagementIP
device password (default is usually cisco)
en
password (Management password)
no fixup protocol smtp 25
write mem
Remember to run these command all firewalls at each site. Once is
done, telnet to the Exchange server with port 25 and you should get a
normal response:
220 ExchangeServerHostName.Domain.com Microsoft ESMTP MAIL Service ready at Day, Date Month Year, Hour:Minute:Seconds +TimeZone
As soon as we did this on the ASA, mail started flowing without hassles.
Best Answer
It sounds like the Exchange server can't communicate with a Domain Controller. Can you give us some specifics on your setup.