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.