When you run Outlook in non-cache mode, or connect using Outlook Web Access (OWA), you access the Global Address List (GAL) directly. Any changes made will appear as soon as your AD forest is replicated.
When you run Outlook in cache mode, you are viewing an offline copy of the GAL called an offline address book (a.k.a. offline address list). By default, Exchange rebuilds the OAB once a day. Also by default, Outlook downloads the OAB once when you launch it - thinking it doesn't need to check more often because of the rebuild schedule.
If you need to force a new entry to show up immediately, you need to do two things. First, manually rebuild the OAB. Open the System Manager (ESM) and expand Recipients then click on Offline Address Lists. In the right pane right click Default Offline Address List and select Rebuild. You should then wait anywhere from 2 to 10 minutes (depending upon how many entries are in your GAL). Second, in Outlook (running in cache mode) go to Tools-->Send/Receive and select Download Address Book. You should then see the new entry.
If you wish to view or change the rebuild schedule, open the ESM and expand Recipients. Open the properties of the particular OAB in question. On the General tab, there is a field for Update interval. By default this is set to run daily - early in the morning. If you wish to have the OAB rebuild more than once a day, you can select "Use custom schedule" and create your schedule.