Adding a new user to exchange? Notice that the new user doesn’t show up in Outlook?

Open up the power shell on your Exchange server (or connect remotely to it), and run the following command:

Update-OfflineAddressBook "Name of Address Book"

Or

Get-OfflineAddressBook | Update-OfflineAddressBook

Then, if you’re in cached mode (most are), you can go to Tools, Send/Receive, and then select Download Address Book
Uncheck Download changes since last Send/Receive and hit OK
Now you should have the new user in your address book!