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.
Is there a reason why creating them as external mail contacts in Exchange doesn't meet your needs? Maybe I'm missing something but creating Mail Contacts should do this just fine. You will then get them as part of the global address list to do with what you please, and IIRC that would include pushing out to Exchange ActiveSync users.
Just tested creating a mail contact in the GAL here, it creates an alias in the GAL that you can do whatever you wish with. Looking at the test object I've just created, it includes fields for address and phone info, but I've not tested phoning that user, that's not a scenario we have here.
Having tested this, I created a mail contact and put my home email and office phone into it. Just emailed home and called work phone via an Exchange ActiveSync account on my iPhone successfully. So there's nothing fundamentally preventing it from working, its all down to how the device implements it, I guess.
Best Answer
the only solution I have found is using the mailContact method. This is a hassle because you then have two lists, AD users and then the new contacts. There is no need to export the Domino address book as all the users are already in AD and have the mail attribute set. So what I did is created a powershell script that reads AD and creates a new contact for each AD user. It will remove existing contacts before adding the new one to keep the list upto date. I am going to run this on a schedule. Its not the best way but it seems to be the only way to do this.