If you are running a local OAB and are operating in cached mode in Outlook, the address book is only updated every 24 hours. You can resolve the issue several ways:
Force the OAB to regenerate:
In Exchange 200x, start ESM.
Open Recipients, then Offline Address Lists.
Right click on "Default Offline Address List" and choose "Rebuild".
Wait - this may take a while depending on how large your address list is.
Change the rebuild schedule for the OAB. This
isn't recommended by Microsoft, but you may wish to implement it:
In Exchange 200x, start ESM.
Open Recipients, then Offline Address Lists.
Right click on "Default Offline Address List" and choose "Properties".
On the first tab, adjust the "Update Interval" to "Use Custom Schedule".
Click on Customize.
Select which hours you want the update to run. The frequency should depend on the size of your address book and how frequent the changes are made.
A good suggestion would be to run the update three times a day - approx 6am to ensure that early starters get their updates - approx middy to catch any changes made in the morning - approx 6pm to catch any changes made during the afternoon.
Ask the clients to download their address book again:
Tools, Send/Receive
Choose "Download Address Book...".
Click OK to the option.
The timescale for Outlook 2003 to download a new address book automatically cannot be changed and is fixed at every 24 hours. In between those you must force Outlook to download it, either by restarting Outlook or using the "Download Address Book" command.