Microsoft Teams のチャット履歴内の検索ツールを使用して、特定のメッセージやスレッドを検索する
こちらでは、ご自身の組織の設定はわからないので、
ご自身の組織のIT,Teamsに関する管理者に状況を説明して相談しましょう。
必要があれば、管理者からMSサポート(または購入先のCSP)へ連絡して支援してもらえます。
チャットやチームから削除しただけでは、組織のゲストとしては削除されませんが、
「念のため、当該ユーザーの削除・追加をしてみた」
とあるのは、ご自身の組織の管理者にゲストアカウントを削除してもらってから、
もう一度、組織に招待し直したのでしょうか?
もし、違うのであれば、
管理者にゲストアカウントを削除してもらってから、
もう一度組織に招待し直してみてはどうでしょう。