@Mike Williams Apologies for issue!
This is due to new feature App Service recently rolled out a Name Reservation feature to protect customers from the threat of subdomain takeovers.
This new built-in feature creates a name reservation for web application names. No additional changes or configuration are needed by the customer to establish a name reservation.
The name reservation for a given resource name will exist from the moment the resource is created and for a lengthy time period after the resource has been deleted (a cooldown period). This means that during the cooldown period after resource deletion, other subscriptions outside of the original creating Azure AD tenant will not be able to create a web application using the same name.
However, once the cooldown period has ended, the name reservation will be released, and any subscription will then be able to create a web application with that given name.
See: Name Reservation on App Service for Web Apps and App Service Environment (ASE)
Also, could you please share what is your Quota ID if its enterprise or CSP or others to help you better on this?