Hello @Jonathan,
I'm glad to hear you were able to resolve your issue by consulting with our support team and thank you for sharing your solution to help others who may encounter the same problem! Since the Microsoft Q&A community has a policy that "The question author cannot accept their own answer. They can only accept answers by others ", I'll repost your solution in case you'd like to "Accept " the answer.
Issue: Custom domain name verification is not working with MX or TXT while the records are seems to be right
Solution: After consulting with our support team, it was confirmed that the domain you are trying to verify in your Entra tenant is already registered in another tenant. This domain was initially registered approximately 20 years ago.
As a limitation, a domain name can only be verified in a single directory at a time. If your domain name is currently verified in another directory, it cannot also be verified in a new directory. To resolve this duplication issue, you must remove the domain name from the old directory. For more information about deleting domain names, refer to the article: Manage custom domain names.
If you have any other questions or are still running into more issues, please let me know. Thank you again for your time and patience throughout this issue.
Please remember to "Accept Answer" if any answer/reply helped, so that others in the community facing similar issues can easily find the solution.
Thanks,
Raja Pothuraju.