A user may not appear in address books if they have been a rehire and the rehire script was not used. This leaves an artifact where msExchHideFromAddressLists is still set to True, making them not appear.
To fix this run powershell, find that value from this command:
Get-ADUser -Identity $username -Properties * | select msExchHideFromAddressLists (where $username is the user name)
This will display a True or False, True being what we expect to cause the issue.
Then run:
Set-ADUser -Identity $username -Replace @{msExchHideFromAddressLists=$False}
This will fix that issue, and can take 30 minutes to sync on web and 72 hours to clear cache on application.