Troubleshooting Error 0xC004F042 after installing new KMS key

We recently installed KB 2757817 on our Server 2008 SP2 KMS host to support Server 2012 installations. Following the instructions, we used the slmgr script to install the new Server 2012 product key and activate the KMS host. However, after doing so, attempting to activate a Server 2012 client using slmgr /ato gave us error 0xC004F074 suggesting that it could not contact the KMS server. After ensuring that the KMS server was accessible from the client and that the DNS records were registered properly, I checked Event Viewer on the client and found this entry:

Log Name: Application
Source: Microsoft-Windows-Security-SPP
Date: 10/14/2012 11:24:07 AM
Event ID: 12288
Task Category: None
Level: Information
Keywords: Classic
User: N/A
The client has sent an activation request to the key management service machine.
0xC004F042, 0x00000000,

According to KB 938450, this error means a mismatch between the client and server KMS keys, however the KMS host was properly reporting the key as VOLUME_KMS_2012_C. I found a thread that suggested removing the key, rebooting, installing the key, activating and rebooting again to resolve a similar issue with 2008 R2. Given that this is a production system, rebooting outside of a maintenance window isn’t possible, however, that gave me the idea that the KMS service may cache the key. Sure enough, after restarting the Software Licensing Service on the KMS host, we could successfully activate Server 2012 client systems.