Rebuild the Offlien Address Book in Exchange System Manager.
Your Outlook client is configured for Cached mode and Cached mode uses the OAB rather than GAL.
Note that depending on organization size, changes to the OAB can take up to 48 hours to show up.
You can force the client to downlaod the address book under Tools, Send/Recieve, Download Address Book.
I hope you find this post helpful.
Regards,
Mark