I have today a problems with one user that we have rename from one name to another, was missing from the address list in Outlook.
The problems was that if the E-mail address in Active Directory Users and Computers, under tag General, was not the same as the users default email address in Exchange 2007.