You place the mailbox on hold, but delete the mailbox. The search cannot be removed while there is a hold. So..you need to remove the hold. You can do this with a remote powershell session and this command:
Set-MailboxSearch -Name Searchname -InPlaceHoldEnabled: 0
Wait a minute, refresh the compliance page and the in-place hold should be = NO
Then you may delete the hold.
Updated 9/30/22 – See Microsoft 365 PowerShell connect to Exchange tenant | IT by Mitch (mitchellenright.com)