Rhoderick Milne blogged about some issues that may arise when verifying domains in Office365.
Just like buses, issues seem to come along in batches. In the last few customer engagements there have been a few issues with adding custom DNS domains into Office 365. Should this not be straight forward you say? Yes it should, but when we add in some deployment complexity and some interesting customer activities it leads to challenges….
The crux of the issues that I run into revolve around adding domains that were previously verified into other tenants. The domains were not removed, and were still present and active in other tenants. A domain can exist only in a single tenant at a given time. If the domain validation process was completed in a tenant and never removed, that domain cannot be then added into another tenant.
Read more at source: http://blogs.technet.com/b/rmilne/archive/2015/09/11/issues-verifying-office-365-domains.aspx