New users not showing in Global Address Book

We are having issues with new users not showing in Global Address Book.
The things that I have done so far:

- When I check OWA the new users show up.
- Clients Outlook is set to cached Exchange mode. When I delete the offline address book folder (C:\Users\testuser\AppData\Local\Microsoft\Outlook\Offline Address Books) and download the “global address book”, all new users show up in the list. If I try to download the address book after that the download task just halts at processing.
- On the server I ran Update-OfflineAddressBook "Default Offline Address Book" and get no errors.
- Get-OfflineAddressBook | Format-List *


- Test email auto configuration displays no errors and the OAB URL path matches the GUID from the Exchange Offline Address Book.

Any help will be greatly appreciated.