I too am seeing this issue.
My scenario is slightly different.
I have deleted Web App from one Azure Directory and now can't create one with the same name in a second Azure Directory
I can create and destroy a the Web App in the original directory as many times as I wish without issues.