How to release server 2008 license from a VM so I can use it on physical box

You can transfer licenses once every 90 days provided they are NOT OEM licenses (and if it was installed in a VM, it shouldn't be).  The only exception is if the hardware fails - but since this is a VM, that exception doesn't apply.

Windows Server keys are multi-activations, so you can re-use the same key on the physical machine without consequence.

If you like however, you can uninstall the current product key by going into Command Prompt as Administrator and typing

cscript c:\windows\system32\slmgr.vbs /upk

Select allOpen in new window

If it tells you you need to specify the Activation ID to uninstall, then you can find the activation ID's by viewing all your license information

cscript c:\windows\system32\slmgr.vbs /dli all

Select allOpen in new window

You essentially cannot "deactivate" a Windows License, which is why they allow multiple activations (within reason).

leew - What is the process for transferring the license?

I used LesterClaytons command line suggestion and removed the product key from my virtual machine.  I then attempted to activate this product key on a physical box and this failed with the stated reason being that the key is allready in use.

destroy the virtual machine.

and use the key on the new physical server and Reactivate, any issues call Microsoft License Activation team

Can I use an evaluation copy of server 2008 and then enter the new product key ?  Is there anything stopping me from doing that?

There are several different type of keys: retail, OEM, MAK, KMS. Only KMS key can be transferred. If you have already activated the other keys they stay with the machine. Uninstalling the key does not reset the activation counter. That way you were unable to activate it. Your only option, as @hanccocka pointed out, is to call Microsoft Clearence Center and ask them to free the activation. OEM key always stays with the machine.

However, each Windows 2008R2 comes with physical and virtual key. If you haven't use the physical key, you should be able to activate it.

I've worked with Microsoft products since before they required activation.  In that time, I've installed hundreds, possibly thousands of times for clients and my employer. I've NEVER had an instance where IF I was denied activation through the internet, Microsoft's licensing phone number failed to provide activation for me.  In that time, I've answered, read, or participated in hundreds of questions involving licensing and activation and I think I've only heard of ONE... MAYBE TWO instances where someone else was denied phone activation.  It happens, but it's rare.  As long as you are doing things within the terms of the license agreement, there is no reason for you to be turned down.

Further, Microsoft's activation systems are not well documented publicly (at least not that I've ever seen and that includes sitting with the product groups in Redmond who are in charge of this stuff (they don't like speaking about it).  But my impression, based on experience and the frequency in which I've had to call is that Microsoft may not track total activations over the life of the key... or they may but not enforce it.  I suspect it resets 90 days after the initial activation.  Or their activation database accepts re-activation after that time.  But again, this is pure speculation based on my experience.  And if anyone has any definitive evidence on how the system works, I'd be happy to read it.