Skype for Business 2019 fails to search address book.

Skype For Business 2019 - On premise

When trying to search for any users by first or last name we receive error message "We couldn't find an exact match. Try refining your search"

There isn't any Galcontacts.db present in the localappdata. Search only works when looking up users by SIP. Entering a SIP address returns the correct result with picture, presence, etc...

Notification at the bottom right is "Cannot Synchronize Address Book"

Skype Configuration -

Gal Status - "Cannot synchronize with the corporate address book. This may be because the proxy server setting in your web browser does not allow access to the address book. If the problem continues, please contact your support team"

We believe the issue is related to TLS. We get the following error message on our Front-end server System logs - Event 36871 - A fatal error occurred while creating a TLS client credential. The internal error states is 10013. The SSPI cleint process is w3wp (PID: 1076).

Another error in the Lync Server Log is - Event ID 4096 - LS web Components Server - "An unhandled exception was encountered. Service: WebTicketSercvice, exception details: System.ComponentModel.Win32Exception (0x80004005)" The client and server cannot communicate because they do not possess a common algorithm at system.Net.SSPIWrapper.AcquireCredentialsHandle.