This sounds as it could be normal behaviour.
Outlook 2007 in cached mode uses the offline address book which gets generated once every night and after that it might take some hours before this OAB gets downloaded to the clients.
So if you wish to speed things up after creating a new user you must generate a new offline address book and then have the clients download this new OAB.
If you wish to force the GAL address book to refresh you need to run "rebuild" in the recipient update service.
Recipient Update Services
Recipient Update Service (Right click and select rebuild)
Outlook 2003 does have a cache mode, to check if it is being used
view or change existing e-mail accounts
I check if the "Use cached exchanged mode" is ticked.
Be aware this mode is required to use the "Junk email filter"
Hope this helps