Some points that may come in handy when troubleshooting KMS Activation Errors:

KMS SRV records are not automatically removed from DNS when the server is no longer acting as a KMS. Therefore, if you change a server's key (so that it is no longer a KMS), remember to remove the SRV records from DNS.

KMS Servers are contacted in the order in which the SRV records appear in DNS. If the KMS server is not active, it should be removed from DNS. If temporarily unavailable, try forcing the client to point to a different KMS server with slmgr.vbs -skms <FQDN of KMS> and see if that works. It is possible that the client will try to contact the offline KMS and not failover to the online one.

KMS SRV records are the VLMCS records located under _tcp under your domain.
The default record properties are as follows:
Time-to-live: 3600 seconds 
Record type: SRV
DNS priority: 0
DNS weight: 100
Service port number: 1688

Most of these settings can be verified by looking in DNS. The Time-to-live value can be verified by running a WMI query against the MicrosoftDNS_SRVType class of the root\MicrosoftDNS namespace.