Old Exchange "Microsoft Federation Gateway" preventing domain validation in Office 365?

Problem Solved

Office 365 support escalation finally confirmed that it was a federation trust that was blocking my validation. I indicated this to support on day 1 when I saw the message and did my due dilligence confirming I had one (and removing it). My original federation trust removal was incomplete, likely due to my expired federation certificate.

Once Microsoft support had someone verify the cause, handling this was simple.

1. Prove ownership again in the way support asks. This consisted of showing my DNS to rule out user error, as well as adding another manual TXT record for validation and letting it propagate (this is good - they aren't going to remove someone's federation trust until they are certain beyond all doubt that you own the domain)
2. Microsoft Support removing the old federation trust on their side
3. Re-running Confirm-MsolDomain -DomainName and seeing the sweet, sweet text

The domain has been successfully verified for your account.

Once support escalation looked at and confirmed what was blocking my validation, Steps 1-3 only took an hour. Getting to step 1 took 7 days of calls, emails, and escalation. :(

Things I tried that didn't work

Removing my original federation gateway using this guide:

Do not follow the steps in the link below mentioning -Force. - I have sent a feedback link that using -Force may have been very bad advice https://support.microsoft.com/en-us/help/3215278/-1007-accessdenied-error-when-you-try-to-delete-the-federation-trust-i

Re-adding and removing a Microsoft Federation Gateway (after asking support if it was fine if I do this). This process went fine and with no errors, but did not solve the original improper/incomplete removal of a gateway. Only Microsoft Support could take care of that. I was hoping that old remnants might either block re-creation (further confirming the issue), or reconnect to the old one and remove it. Not the case, at least for me. Maybe if I renewed & re-used my old cert (this is the self signed cert federation trust steps have you create, not your main exchange SAN)? That will remain an open question.

Numerous validation attempts at the request of support.

Lessons / Guidance

If you too find yourself with an old, forgotten "Microsoft Federation Gateway" on your Exchange server that you are certain was not being actively used and has an expired federation certificate, renew the certificate before removal! I used -Force (per docs, when encountering the error I had) and that may have caused my issue. Emphasis on may but I think it's likely as I have no other explanation. Support confirmed it WAS a federation trust blocking my validation, but did not definitively state why it was still there - the suspicion is the expired certificate when removing and that seems the most likely.

Document everything. Good discipline w/ logs, error messages, and screenshots are how I saw this error. The error message that indicated my true problem only displayed ONE TIME out of a dozen attempts with support. Every other time it was a generic "verification failed. Contact Support". Had I not documented this, searched, and read up that a trust may be blocking this, I would not have been pointing support in this direction and I may have been stuck trying to resolve this for much longer.

Office 365 support is slow. I didn't expect it to be fast, but I expected a lot faster than 7 days to solve a deployment blocker. Verify your domains WAY before you need them, in case you hit an unexpected issue.