HOWTO: Resolve “Cannot find the physical computer that runs the virtual machine.”

I recently ran into this problem when I had to set up Direct Access with a Hyper-V machine.  See here for the cause and resolution (Thanks thompal)!

From Thomas:

The solution:
-go into the Registry and delete "HKLM\SOFTWARE\Policies\Microsoft\Windows NT\DNSClient\DnsPolicyConfig"
-in an elevated command prompt, enter: sc control dnscache paramchange

After that the “Virtual Machine Connection” was working fine.