A sysprep doesn't rearm the office installation on the client. As a result, the CMID will be duplicated and the client office will be deactivated after 30 days.
The fix for this issue and getting the count to increase (and finally activate) was to run a re-arm utility provided under program files (or program files x86, depending on your installed flavor):
C:\Program Files\Common Files\Microsoft Shared\OfficeSoftwareProtectionPlatform\ospprearm.exe
Running the utility under an elevated command prompt will then show completed successfully. If you wish to double check you can then run ospp.vbs with the /dcmid switch and find that there is now no Client Machine ID.
Once this is compelte, run your sysprep as you would and you will find that for each client that you activate from now on for your KMS will increase your count. You will also find that if you have some clients with the same ID then they will also all activate.