I’ve run into this a few times, thought I’d record the solution for once so I remember it.
After adding a new user account, the user does not show up in Outlook’s Global Address List, but does show in All Users. (If you click “To” in a new message, for example, and in the Select Names windows under “Show names from the:” drop down, you select All Users.) Even if I go into Active Directory Sites and Services and manually force replication it does not work. (under the NTDS Settings for each server) Normally, I would even go into Recipient Update Services and manually update, but this does not work either.
I found out that if you have Outlook in Cached Exchange Mode, the Global Address List does not update for up to 24 hours. I don’t know the details on that, but I can force it to update. This is on a per-machine basis, so doing this across the whole network won’t work. (Although, there may be a way to do this, I just don’t know how.)
Go into Outlook, go to Tools, Send/Receive, then click Download Address Book. Make sure you have Global Address List under the Choose Address Book drop down, and click OK. Problem solved.
By the way, I am using Exchange 2003 and Outlook 2003.