What is the proper way to change the product key for Office 2010 Professional Plus?

I am trying to clone a VM. I've done sysprep successfully and all is well with my new box, except Office 2010 Professional Plus product key did not get wiped by sysprep (not too surprising), and I am unable to change the product key.

1. When first starting outlook on the new box, activation is required. It tries to activate using the old product key.
2. After attempts to change the product key using one of several different methods, the product will no longer run, complaining that it cannot verify the product key.

Methods of changing product key that I tried:

1. Control panel | programs and features | select office 2010 | change | change product key.
2. Running "ospp.vbs" as explained in Microsoft Technet article Tools to configure client computers in Office 2010.
3. Deletion of registry keys "ProductId" and "DigitalProductId" as explained in Microsoft KB article 2581695: Office 2010 product key change error Step by Step.
4. Various combinations of the above.:)

Results of trying the above:

1. With simple approach (sysprep then running outlook on new VM), outlook wants the product to be re-activated. This results in an error message indicating that the old product key has reached its maximum number of activations. (And I want to use a new product key anyway.)
2. After entering a new product key using one of the above methods, office products will not start. They give the error message "Microsoft Office Professional Plus 2010 cannot verify the license for this product. You should repair the Office program by using Control Panel." Unfortunately that suggestion does not change anything.

What I want to happen:

• I want the ability to enter a new product key and then go through activation, and have Office products working under the new product key in the new VM.

The system I am trying to clone is running Windows 7 Professional 64-bit.

NOTE: I am unable to use MAK or KMS. I must use individual keys.

I contacted Microsoft (MSDN) Technical Support and received step-by-step instructions that almost worked. I tweaked them a little and got them working. Since I cannot find the following working solution anywhere on the interwebs, I thought I should post this information for others. (Prior to contacting Microsoft, I did find and try many solutions, but none of them worked.)

Here is what worked for me:

1. Go to services.msc and stop the "office software protection platform" service.
2. Rename three files:
   • In %ProgramData%\Microsoft\OfficeSoftwareProtectionPlatform\ - rename tokens.dat to tokens.dat.old
   • In %ProgramData%\Microsoft\OfficeSoftwareProtectionPlatform\Cache\ - rename cache.dat to cache.dat.old
   • In C:\Program Files (x86)\Common Files\microsoft shared\OFFICE14\Office Setup Controller\ - rename pkeyconfig-office.xrm-ms to pkeyconfig-office.xrm-ms.old
   • Note: The path above for "C:\Program Files (x86)\" might be just "C:\Program Files" depending on the OS.
3. Launch any office application. (I used Outlook.) A repair occurs and you are asked if you want to restart the OS.
4. DO NOT RESTART.
5. A second operation begins. You are prompted for a product key.
   • I'm guessing you can just cancel out of this, and install the product key using only the steps below for ospp.vbs.
   • However, in my case, I entered the product key and clicked "continue".
6. Close the office application.
7. Launch command prompt with administrator rights.
8. Browse to path C:\Program Files (x86)\microsoft office\Office14.
9. Type in the command cscript ospp.vbs /inpkey:xxxxx-xxxxx-xxxxx-xxxxx-xxxxx
10. Type in command cscript ospp.vbs /act

I hope the above information helps someone in a similar situation.

If I remember correctly Office 2010 Professional is activated either via KMS or MAK now. If you have a kms sever in your environment, use slmgr.vbs, more info here.

Update

Yes, either MAK or KMS http://technet.microsoft.com/en-us/library/ee705504(v=office.14).aspx

Update2

Have you went to file->Help inside of an Office Program?