HI,
I have noticed only some newly created users had the issues. Whats your exchange version?
You could restart the Microsoft Exchange System Attendant service to have a try.
If the issue persists, your server is exchange 2013,please check if the OAB file can be generated in %ExchangeInstallPath%\ClientAccess\OAB\ folder.
If its prior to exchange 2013 ,please check the OAB file in %ExchangeInstallPath%\ExchangeOAB folder.
On your server side, please run the following command to add a new OAB :
Set-OfflineAddressBook -Identity "My OAB" -IsDefault $true
if it doesn't work,please check your autodiscover service:
Get-ClientAccessServer | FL Identity,AutodiscoverServiceInternalUri
On the problematic client side, please run Test E-mail AutoConfiguration Tool to check if the client can get the OAB URL,and collect the Logs tab and Results tab information.
Also you can recreate a new Outlook profile to test on the problematic clients.
Best Regards,
David