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. 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 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 , I had to run setup. 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.