Symptoms
In Microsoft Lync 2013 (Skype for Business), a partial-name search on common names displays a wrong result of 'No Matches'. It should say 'Too many matches' and ask users to refine search parameters.
Resolution
To fix this issue, installĀ MS16-097: Description of the security update for Lync 2013 (Skype for Business): August 9, 2016 (KB3115431). Note Lync 2013 was upgraded to Skype for Business in April 2015.