Rebuild your GAL on the exchange server.
Hit the Start button and select "All Programs." Click to open "Microsoft ExchangeServer." Select "Exchange Management Shell." This will launch a new window with a command prompt. Please note that you will require administrative privileges to access this utility.
Type "get-offlineaddressbook | update-offlineaddressbook" without the quotes. Press "Enter."
Wait till the Server "rebuilds" your default Global Address List. Depending on the size of your GAL, this process may take several minutes to complete. Close down Management Shell when the rebuild process completes.
Manually download the GAL in an Outlook client to confirm the addresses are now correct