Issue: 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 address book.  It appears update-recipient is working correctly on Exchange 2010, but not Exchange 2007.

Cause: 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. 

Resolution: 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:

Additional Information:
GALSYNC Resource Wiki: