In Microsoft 365 / Exchange Online, to connect a soft deleted mailbox, you have need to use the cmdlet New-MailboxRestoreRequest to restore the mailbox to another user.

Get-Mailbox -SoftDeletedMailbox | select guid

Get-Mailbox <NewMailbox> | select guid

New-MailboxRestoreRequest -SourceMailbox <GUID> -TargetMailbox <GUID of new mailbox> -AllowLegacyDNMismatch

To check the status of the restore:

Get-MailboxRestoreRequest | Get-MailboxRestoreStatistics

References:

Reddit