This issue seems to be more prevalent today due to the various tools used to clone images, create images based on a templates, Physical to Physical (P2V) tools, etc...
Generally the symptom you will see is that the count on your KMS host will not show the correct number of clients or it will not increase. There are a number of reasons why this can occur but a common reason is that sysprep was not used when preparing images for deployment.
Any time you use imaging as your deployment method it is required that you run sysprep to prepare the image for deployment.
This policy is outlined in the following KB article: http://support.microsoft.com/default.aspx?scid=kb;EN-US;162001
To determine if you are encountering this you can use the Key Management Service Log do the following:
1. On your KMS host open Event Viewer
2. Right click the Key Management Service Log and choose “Save all events as”
3. Change the Save as type to Text(Tab Delimited)(*.txt)
4. Save the file as KMS.TXT
5. Close out of the Event Viewer completely
6. Open Excel
7. Click File, Open, and browse to KMS.TXT
8. You should see the Text Import Wizard. Choose the following options
Start Import at Row: 8
9. When complete the data may look all messed up. Don’t worry we will correct that
10. Click the upper left of the spreadsheet to select the entire spreadsheet
11. Click Data, Sort, In the Sort By selection choose “Column D”
12. When complete you should see the data sorted in columns.
The Client Machine ID (CMID) is how we uniquely identify a KMS client. When sysprep is run one of its jobs is to generalize this GUID so when the image is deployed every machine has a unique CMID. Here is an example output
While it is possible to run slmgr.vbs /rearm to reset the machines CMID that does not leave the machine in a supported state. Images deployed without using Sysprep to prepare the image are not supported by Microsoft. Sysprep executes ~30 sysprep providers. These providers are written to correct issues with various components when you duplicate the installation. By not running sysprep it is unknown what types of issues you could encounter and many components will be in a broken state. The supported solution is to rebuild the image using the Sysprep /generalize switch and redeploy the systems.