We've been having similar issues here with performance of Windows Server 2008 x64. Initially we deploy our machines from template with minimal resources allocated (1CPU, 512 MB RAM). We then deploy the VM from the template and once the machine has deployed completely, log in, shut it down and reconfigure its hardware to whatever is required.
I noticed that after reconfiguring a VM to 2CPU and 4096MB RAM that boot time was extremely slow (several minutes, compared to the template which boots in around a minute). Also general response from the VM was slow and Task manager showed 100% CPU Utilisation for extended periods when trying to complete simple tasks like opening Server Manager etc. This behaviour was consistent for all 2008 X64 VM's.
Firstly we noticed that inexplicably the VM is configured with a 512MB memory reservation. This is not configured on the template. Still after removing the memory reservation boot times and performance remain just as poor as before.
The solution we came up with was to shut down the VM, return the Virtual Machine memory to 512MB, boot the VM, shut it back down and set the memory back to the desired amount.
Why this works is a mystery and I'm still not convinced that this is a viable solution. I try to avoid working in the paranormal.