Creating contacts in Exchange Admin Center generally takes 24 hours for it to update and show in the address book for users. Below is a method to manually push the contact to their address book

Run in Exchange Management Shell

Get-OfflineAddressBook "Default Offline Address Book (Ex2013)" | Update-OfflineAddressBook

Client side:

1. Click File tab, Click on Account Settings, and then click Download Address Book.
2. In the Offline Address Book dialog box, make sure that the Download changes since last Send/Receive check box is checked.
3. Click OK.