Hello @Petteri,
Thanks for reaching out to Microsoft Q&A.
As we discussed. Create a new App Service Plan and App Service using the same names as the deleted ones, integrate the App Service with the VNet subnet, then disconnect the VNet integration and delete the subnet.
Reference Thread: https://v4.hkg1.meaqua.org/en-us/answers/questions/140197/unable-to-delete-vnet-due-to-serviceassociationlin
Kindly let us know if the above helps or you need further assistance on this issue.
Please "Accept the Answer" if the information helped you. This will help us and others in the community as well.