We have the same problem in vRA 6.2.1
The machine is not in AD,DNS,WINS and is not in vCenter
We ran an inventory in vRA on the cluster/s in question to bring it up to date with the vCenter inventory and it still fails saying the machine exists
what else can be checked?
I was having the exact same issue. I deleted the computer objects out of AD, out of DNS, and out of VC and it was still giving me the error that the machine name already existed. As a final attempt i ended up doing another full data collection on the compute node that was holding the machines before they were deleted (i had originally run a full data collection right after i deleted it from VC but it was still in DNS and AD). After the second data collection finished i was then able to provision the machine with the same name again without it giving me the error. The key here seemed to be that i had to remove it from AD,VC, and DNS first, wait for the DNS and AD changes to replicate and then perform the inventory. Not sure if that's your issue but hopefully it will help.
Edit: Also, just in case someone else runs across this, if you provisioned the machine previously through VCAC and just deleted it from virtual center it will not automatically remove the machine from the VCAC inventory. Even if the VM is deleted in vCenter you will need to go into VCAC and find the machine and select "Destroy" to actually get rid of it.