Re-deploying the API management service fails and help says call the REST API: here's a script to do it.

Remove-SoftDeletedAPIService.ps1

<#
    .synopsis
        Remove Soft-deleted API Management service
    .description
        Re-deploying the API management service fails with a message
        See https://aka.ms/apimsoftdelete
        That says call the REST API. This does that.
#>
[cmdletbinding(SupportsShouldProcess=$true,confirmImpact='High' )]
param (
        #Specify name of APIManagementService
        $name = "*"
)
$subscriptionid  = (Get-AzContext).Subscription.id

$authresp        =  Get-AzAccessToken -ResourceUrl  $managmentUrl
$headers         = @{Authorization = "Bearer $($authresp.Token)"}


$uri = "$managmentUrl/subscriptions/$subscriptionid/providers/Microsoft.ApiManagement/deletedservices"

Invoke-RestMethod  -Headers $headers  -Uri ($uri + "?api-version=2020-06-01-preview") | Select-Object -ExpandProperty value |
    Where-Object -Property name -Like $name |  ForEach-Object {
        if ($PSCmdlet.ShouldProcess($_.name , 'Remove soft-deleted ApiManagement Service')) {
            $u2 = "$managmentUrl" + $_.id + "?api-version=2020-06-01-preview"
            Invoke-RestMethod -Uri $u2  -Headers $headers -Verbose -Method delete
        }
}