KMS for Office 2013 defaults to old server – DNS is fine

I have a strange problem with a Server 2012 R2 KMS Server which has been migrated from a 2008 R2 Server – and by migrated I mean removed, and followed all instructions found here: http://www.rivnet.ro/2013/02/how-to-remove-a-kms-server-from-your-infrastructure.html

The new server is Windows Server 2012 R2: Mercury

The old server is Windows Server 2008 R2: Europa

What I am finding is that when doing a ospp.vbs /dstatus the server is coming back as the old server:

KMS machine name from DNS: europa.:1688
KMS machine registry override defined: europa.:1688

I manually change the kms host:

\ospp.vbs /sethst:mercury.

Then do a /dstatus again which shows:

KMS machine name from DNS: europa.:1688
KMS machine registry override defined: mercury.:1688

If I run:

nslookup -type=srv _vlmcs._tcp

on the troubled clients, I get:

_vlmcs._tcp.(domain)   SRV service location:
      priority       = 0
      weight         = 0
      port           = 1688
      svr hostname   = mercury.
      mercury.       
      internet address = 192.168.6.218

So from that, I can gather that the DNS is set correctly, but for some reason there is an over-riding setting that is forcing the client back to the old server, even after manually setting the server name.

I ran:

ipconfig /renew

and:

ipconfig /flushdns 

on these machines and most have been rebooted too.

As soon as I try to activate, either using "/ato" or using the Volume Activation Management Tool 3.0 it will immediately revert to using the old server name.

What could be the cause of this as it is doing my nut in!

Thanks all.