What Operating system are you using?
How are you activating windows (MAK or KMS)?
Windows7 on the VDI, and we have KMS for the windows activation.
Is the KMS server actually getting the requests though? I had an incident before where someone installed a new kms server which updated dns and none of my desktops could find the kms server. I manually specify it now.
As above, check for any rogue KMS servers that have registered in DNS - they will automatically create an SRV record with "_VLMCS", so are very easy to spot.
Past that, the following article should identify the issue quickly: