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.
Open PS in administrative context
Run: Set-ExecutionPolicy RemoteSigned
$LiveCred = Get-Credential
$Session = New-PSSession -ConfigurationName Microsoft.Exchange -ConnectionUri https://outlook.office365.com/powershell-liveid/ -Credential $UserCredential -Authentication Basic -AllowRedirection
NOTE: When prompted for credentials, enter your Office 365 admin username/password or one that has admin rights for the tenant.
After you’re done: