I suggest you check the Availability Set is listed under Azure Resources portal and to fix it from there.
This kind of issues might come, when the resource removal is not followed as per Microsoft recommendation.
Are you able to locate the Availability Set under resources.azure.com portal something like below?
You can try a force Update the resource.
Hilight the resource and in the right pane, click Edit and then click PUT to forcefully update. If the resource is stuck in a deletion or updating state, the operation helps to resolve the issue in most of the cases I see.
Try a deletion after the above step and see if it helps!
--please don't forget to
Accept as answer if the reply is helpful--