Windows 7 Upgrade Key Issues

I recently bought a Toshiba laptop with Vista installed. It came with a free upgrade to Windows 7 through the mail. I received the DVD and upgraded to 7. Then my genius girlfriend then was nice enough to throw out the DVD packaging with the product key. 30 days passed,and now I need to activate. I called Microsoft to get a replacement key; they told me since the upgrade came from Toshiba, I would have to get a replacement key from them. I called Toshiba, they told me only Microsoft has the ability to give replacement keys and my only option was to restore back to Vista. Has any one else ran into this? Is there any way to fix this? Is the product key stored on the DVD itself anywhere? I'm not trying to rip anyone off or do anything illegal, I just want my legitimate copy of 7 to work.

Download BelArc advisor which will audit all of the keys on your system.

Safeguard the key as you would a $100 currency note.

Save a Win7 Backup Image externally (and to a primary formatted partition if you want) so that you never have to reinstall Win7, just reimage the HD or a replacement in 15 minutes.

Did you originally clean install, booting from the DVD to format then install? If not, you may not have the cleanest possible install. Are you satisfied with it? You can clean reinstall if not.

But first I would preserve the installation as it now exists with a backup image saved in perpetuity as the audited keys are not as definitive as if you still had that key insert, and the backup image WILL hold its activation on the same hardware.