Are you talking the Global Address List, Offline Address Book, or the list as seen from webmail on the Client Access Server?
GAL Updates
The actual GAL (Global Address List) should update immediately upon user creation in Active Directory, but may require replication across domain controllers.
Force a GAL update with PoSh:
Get-GlobalAddressList | Update-GlobalAddressList
OAB Updates
The OAB (Offline Address Book) is updated every 24 hours by default on the Exchange server, configurable through the Organization Configuration.
Force an OAB update with PoSh:
Get-OfflineAddressBook | Update-OfflineAddressBook
OAB -> CAS
The replication of the OAB to the CAS (Client Access Server) can take up to eight hours after the last update.
Force OAB-CAS replication with PoSh:
Get-ClientAccessServer | Update-FileDistributionService
Outlook OAB Download
The download of the OAB by cached Outlook clients from the CAS happens at most every 24 hours.
You can force an OAB download in Outlook through Send-Receive settings.
The disconnect is probably somewhere along those lines. If you don't want to go down the line forcing updates, just wait 24 hours and see if you still see issues.