I've spent the better part of this morning wrestling with this one, so I'm sharing it in case others in my situation experience the same problem.
We are currently in an Exchange 2003/Exchange 2010 co-existence period. There are a handful of test mailboxes on our Exchange 2010 server, the rest are on Exchange 2003 and our Offline Address Book generation server is currently the Exchange 2003 server.
Yesterday somebody left the company, so we followed our normal procedure and hid them from all Exchange address lists and waited overnight for the Offline Address Book to be rebuilt. When I got in today, the offending user was still listed in our Offline Address Book. For reference, this users mailbox is on the Exchange 2003 server.
I checked the event logs on the Exchange 2003 server and no warnings or errors were logged in the early hours by the Microsoft Exchange System Attendant service during the OAB Generation process. Thinking this was just a fluke, I manually rebuilt the Offline Address Book with the same results (no warnings/errors and the user still in the Offline Address Book).
There are no synchronisation errors in Outlook and I have verified (using Exchange System Manager on the Exchange 2003 server) that the Offline Address Book does exist and is still being created in the early hours of each morning, as well as when I manually rebuilt it this morning.
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.