I've ran into this multiple times now when trying to deploy an SSL certificate within Azure.
I've created App Service and applied a custom domain name. Then went to App Service Certificates and filled out all the information including the domain name setting. However, when going in to verify the domain certificate it states that there is no App Service with the domain name assigned. I've checked and double checked that I didn't misspell anything. I've also tried to manually verify but it continues to to not see the TXT record update.
The last time this happened it successfully sent the email verification email to the administrator so we were able to work around it (this also verifies that the correct domain name was used in that case) but in this case the administrator email is the domain registration company's default address.
Has this been encountered by anyone? Is there another workaround? MS support has been painfully slow to respond to my tickets.