As discussed offline, we confirmed that domain contoso.com is still not deleted form old.onmicrosoft.com tenant.
You need to first delete the domain from old.onmicrosoft.com completely and then you can add the domain to new.onmicrosoft.com.
We have already helped you in creating a case with support team so that you can prove old.onmicrosoft.com tenant ownership and post that you can delete the domain contoso.com.
Let us know if you have any further questions on this.
Please "Accept the answer" if the information helped you. This will help us and others in the community as well.