There is a good chance that someone mistakenly disabled the user account.
Can you check the soft deleted and inactive mailboxes: Get-Mailbox <Mailbox Name> -SoftDeletedMailbox Get-Mailbox <Mailbox Name> -IncludeInactiveMailbox
You can also check the deleted MSOL user to check if you find the user
If you find the user in any of these locations you can restore it from here Undo-SoftDeletedMailbox Or if you want to create a new shared mailbox and restore the data to it you can run a restore request. New-MailboxRestoreRequest -SourceMailbox <Soft Deleted Exchange Online mailbox> -TargetMailbox <Existing Exchange Online mailbox> -AllowLegacyDNMismatch