Couple of things have to happen before Outlook will display it...

1) The Exchange server has to rebuild the offline address book

    This happens once every 24 hours by default.  If you haven't make any
changes to server configuration, then I think the time is something like 4
or 5 AM.

2) Once the offline address book is rebuilt on the server, Outlook will
download changes once every 24 hours.

Depending on your site, you may decide to have the offline address book
rebuilt more frequently.  For example, the site I work for rebuilds it 3
times a day.   This way the remote workforce has a better shot of getting
new items to show, however we still state that new items will take 24 hours
to show in the GAL.

What else am I missing... oh, you might want to take a peek at:
http://support.microsoft.com/default.aspx?scid=kb;en-us;823580&sd=RMVP

We use this key to suppress downloading of the offline address book for
workstations (those that never leave the site), but not for offsite stuff.
This is about as close as you can get to real-time if you want the client
workstation to use cached mode.