In Microsoft Lync 2013 (Microsoft Skype for Business), when you search for a contact from the address book by entering a few characters of the display name, one of the following messages is displayed in the search result:
Address book synchronizing. Results may be not current.
However, when you enter full name, this contact name is displayed.
This issue may occur if your local GalContacts.DB file contains useless records that contain only a first name and a last name. This situation triggers internal search failure when you search on less than the complete display name. Therefore, no results are displayed.
To resolve this issue, install the October 13, 2015 update (KB3085581) for Lync 2013 (Skype for Business).
Note Lync 2013 was upgraded to Skype for Business in April 2015.