Recently I configured a new Office 365 E3 tenant for my lab environment and one of the domains I use (and had in mind for configuring Federation) was exchangelabs.nl.
When adding a domain to a tenant Microsoft has to verify if you’re the owner of the domain being added and this is achieved by you adding a TXT record to public DNS. Microsoft checks for this TXT and thus knows you’re the one and only owner.
After adding the TXT record the verification wizard failed with the following error:
Can’t verify domain
Exchangelabs.nl was already added to a different Office 365 account exchangelabs.onmicrosoft.com.
Sign in to that account as ad admin, and remove domain <domain>. Then come back here and try adding <domain> to this account again.
If you can’t sign in to exchangelabs.onmicrosoft.com as an admin, try resetting your admin password.
After trying several times over several days (you have to wait for proper DNS replication, although my TTL is set to 10 minutes, and wait for possible Active Directory replication at Office 365) it still didn’t work out.
Also trying to logon to the exchangelabs.onmicrosoft.com tenant did not work, although this tenant didn’t ring a bell at all.
The only thing that’s left is creating an incident at Microsoft support. You can find this in the Microsoft Online Portal under Support | Service Requests. After struggling through the initial response team in India (which took 15 days!) I ended up with an Escalation Engineer at Microsoft support. He explained to me my domain exchangelabs.nl was registered to an orphaned tenant (which was shown as exchangelabs.onmicrosoft.com in the previous figure). It turned out that this was a test tenant I obviously tried years ago, but completely forgotten about it.
For security reasons Microsoft cannot just remove a domain from a tenant, so first I had to add another TXT record to public DNS to prove I’m the actual owner of the domain. Once verified Microsoft approved the removal of the domain and the next day I was able to add the domain to my new tenant and have the domain verified successfully.
The bad thing is that it took quite some time to resolve. The case was logged on October 16, 2014 and was escalated within Microsoft on October 31 (15 days!). When it was escalated it took 4 days to deregister the domain (there was a weekend in between) so the entire issue took almost three weeks.