Found the following article:
New users not appearing in Global Address List -
I suspect that you're using Outlook 2003 with the default cached mode.
Five things have to happen--and in this order--before recipients show up in
the GAL in Outlook 2003 with cached mode, i.e., the Offline Address Book:
1. The object or change must replicate to the domain controller the RUS
uses.
2. The RUS must run and stamp the user with Exchange attributes.
3. The offline address book must be generated. This is a scheduled activity.
4. The OAB system public folder must replicate to the public folder server
the user's Outlook is using.
5. Outlook 2003 must synchronize itself with the offline address book. This
is directed by Outlook.
--
Should i switch back to online mode and download addressbook and then switch back to cache mode?