Thanks for the response. So here is our issue, in a nut shell.
We use non-persistent pools with "delete on log off" set. This is really important to us.
What we are seeing is that DHCP gives out an IP no problem. And the first time the VM is used all is well. When someone logs off and the VM gets deleted, a new one will be created in it's place using the same name. Because the true identity of the VM is not the same, (SID and MAC) it does not get the same IP. It should get a new one and the name should reflect that but it doesn't. The new one will sometimes have the correct name but not allways, when it doesn't the name is the original name with a long number appended to it. So now the dns names are all out of wack and the VM can't be used....
We can manually remove all expired leases and it will fix the issue until the range is used up again, with the "duplicate" names.
A real pain!
