We are trying to add our domain to Azure Active Directory and to verify it with TXT records. But verification fails with error that the domain was previously added in another AAD tenant and that needs to be removed from there before adding it here. We removed it from our O365 AAD tenant and tried adding in Azure again, but it still fails to verify the records added in the web hosting portal for the said domain. We have tried with TXT as well as MX records, but the failure still persists. We have allowed enough time for the DNS propagation, but it doesn't help.
Please help me with your thoughts on this or if any one has come across the same issue and if yes, how it was resolved..
Attached the error screenshot for your reference.