The Connect-Mailbox and New-MailboxRestoreRequest cmdlets fail and return the following error message:
Active Directory operation failed on dc1.contoso.com. This error is not retriable. Active directory response: The search filter is invalid.
The LegacyDN property value on the soft deleted mailbox in the mailbox database is empty.
To fix this issue, install the following updates, as appropriate: