コンテンツ、知識、アプリケーションの共有と管理に使用される Microsoft 製品とテクノロジのグループ。
> SharePoint Onlineで社外の外部ユーザとの共有を行うため、アクセス権を付与しました
この操作でテナントの Azure AD に外部ユーザーがゲストとして登録されるはずです。
> 諸事情で一度アクセス権を削除しました
ここで具体的に何をやったのか分かりませんが、エラーメッセージが「ユーザーがディレクトリに見つかりません」であれば、当該の外部ユーザーが現在 Azure AD でどのようになっているかをまず確認されると良いでしょう。