Symptoms
Some users are not searchable in Lync client (Skype for Business).
Cause
Incorrect AdPartitionId
in Lync database. Related case can be found in
http://www.lyncexch.co.uk/improve-lync-contact-search-without-sharepoint/
Resolution
Please contact Microsoft Technical Support in order to identify the root cause of this issue. As a workaround, you may search using full user name instead of a display name.