Initial that LegacyExchangeDN is not populated on certain contact objects. This was a mixed environment with Exchange 2007 and Exchange 2010. After running Update-Recipient, LegacyExchangeDN is populated on all contacts, but several are still not showing up in the address book. It appears update-recipient is working correctly on Exchange 2010, but not Exchange 2007.
After further examination, it looks like msExchALObjectVersion attribute was not populated for the non-working contacts. Recipient Update Services in legacy Exchange environments should populate this attribute.
Running /PrepareLegacyExchangePermissions, then running update-recipient populated msExchALObjectVersion and allowed the contacts to show up in the addressbook. More information about PrepareLegacyExchangePermissions can be found here: http://technet.microsoft.com/en-us/library/aa997914%28v=exchg.80%29.aspx
GALSYNC Resource Wiki: http://social.technet.microsoft.com/wiki/contents/articles/1726.global-address-list-synchronization-galsync-resources.aspx/a>