Symptoms
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.
Cause
The LegacyDN property value on the soft deleted mailbox in the mailbox database is empty.
Resolution
To fix this issue, install the following updates, as appropriate:
Cumulative Update 12 for Exchange Server 2019 or a later cumulative update for Exchange Server 2019
Cumulative Update 23 for Exchange Server 2016 or a later cumulative update for Exchange Server 2016