Office365を大規模で利用していると、気が付かないうちにですが連絡先からユーザーを検索できなくなるケースがあります。
たいていの場合はSkype クライアントアプリのキャッシュ破損だったりするのですが、時折サーバー側で不調をきたしているケースがあるのでクライアント設定を弄っても変化がないときは手順をためしてみるとよいと思います。
方法はAdmin Centerでユーザーを選択し、Skype for Businessのライセンスを外してから再付与するのみです。
E1やE3の中のものに対して再付与しても問題ありません。
ただ、一度外すと本対象ユーザーを個人の連絡先に登録しているユーザー側でログイン状態が不明となるケースが出てきます。
この状態が発生した場合はそのユーザーに再ログインしてもらうことで通常の状態に戻るようです。
音楽:幕の内ウェスタン