Microsoft Teams のユーザー検索では一度検索を行うと最大 30 日間サーバー上にキャッシュ情報が保持されます。
そのため、削除を行ったユーザーや、Microsoft Teams 管理センター (https://admin.teams.microsoft.com/dashboard) から [組織全体の設定] – [Teams の設定] – [Exchange アドレス帳ポリシー (ABP) を使用した Teams 内の範囲ディレクトリ検索] を [オン] にした上で、アドレス一覧から非表示にしたユーザーに関しても、一定期間検索で表示されることが想定される動作となります。

なお、サーバー上に保持されるキャッシュ情報を任意のタイミングで削除する機能は 2019 年 6 月 25 日現在、実装されておりません。

[Microsoft Teams の範囲指定ディレクトリ検索を使用する]
https://docs.microsoft.com/ja-jp/microsoftteams/teams-scoped-directory-search

－－以下抜粋－－
新規または更新されたアドレス帳ポリシーを適用する前に、既にキャッシュされていたすべてのユーザーデータは、最大30日間はユーザーに対して利用可能になることに注意する必要があります。
－－抜粋終了－－