Hello _MM,
Thank you for posting in Microsoft Community forum.
You can check or troubleshoot the issue as below:
1.How many Domain Controllers are there in your domain? Two or more than two DCs?
2.You can try to check whether the two DNS records mentioned above actually exists or not on both 2016 Domain Controllers.
For example:
gc._msdcs.mydomain.com
3.If you also have other DCs except the two 2016 DCs, you can also check if gc._msdcs.mydomain.com and _ldap._tcp.dc._msdcs.mydomain.com actually exists or not on other DCs.
4.Try to check AD replication status between all Domain Controllers in this domain? Please run commands below on PDC.
repadmin /showrepl >c:\rep1.txt
repadmin /replsum >c:\rep2.txt
repadmin /showrepl * /csv >c:\repsum.csv
I hope the information above is helpful.
If you have any question or concern, please feel free to let us know.
Best Regards,
Daisy Zhou