Consider the following scenario:
You're using the 32-bit version of Microsoft Skype for Business 2016 on a computer that’s running a 64-bit operating system.
The client policy AddressBookAvailability parameter is set to FileDownloadOnly.
In this scenario, the client can't download the global address book (GalContacts.DB file). Therefore, you can't find any contacts when you search for them on the client.
To fix this issue, install the MS15-128: Description of the security update for Skype for Business 2016.