Strange product key issue

I'm wondering if anybody else has ever come across this before. I have a laptop that I got from a relative, who bought it used. It had Windows 7 Home Premium installed on it, but the hard drive got corrupted and had to be completely reformatted. The product key on the bottom of the laptop was intact, but the rest of the label was blurred (couldn't tell what OS it was for), so when I installed Windows 7 again from discs I created from a Digital River download, I entered the product key. It was not accepted. I decided to contact Microsoft and see if I could get any help. Thankfully after a short 5 minute wait, I was speaking with a human being who was fluent in English.

The rep checked on my product key and informed me that it is valid for Windows Vista, not 7. So apparently the previous installation was an upgrade. Unfortunately that information was completely lost, so... I figured OK I'll just install Vista then. Again, the rep told me it is a valid product key.

Well, I go ahead and supply my Vista product key on the Windows Vista installation screen and... I get an "invalid product key" error. What's interesting is that when you enter any variant off of the product key, the error response is immediate. But when I supply the code as I have it noted, the wait icon appears for about 5-10 seconds before coming back and telling me it is not valid. This is simply a checksum verification, as the laptop is not connected to the Internet at this time. So, even if there would be some activation issue, this is happening before it. Is this checksum being validated against an internal reference? I'm now wondering if the motherboard might have been replaced at some point.

Naturally I checked and double checked the product key. I had written it down on a piece of paper, transcribed from the back. This is what I read to the Microsoft rep. I tried re-typing the key exactly a few times and kept getting the same error.

Any ideas? I figured I'd check here first before trying to call Microsoft again (not sure if they can really help me at this point).

Hey Buddy,
Follow these instructions and if your number is valid, you will be up and running quickly.
Activate Windows 7 by Phone - Windows 7 Help Forums

Call them up, as since Vista a OEM isn't allowed to be redone with a previously used key.

Stupidly unuseful to have a key, but if you used the recovery it doesn't ask for it if i remember rightly.

Thanks for the tips, guys. What's strange is that I this comes up even before activation. There are two steps, [1] to enter the product key initially upon installation and then [2] activation either over Internet or other means. Mine fails at entering the product key.

I read elsewhere that people have been able to re-install OEM Windows operating systems with issue, like "I have the same OS installed and have already installed it several times in the last week with no problems re-activating each time." My concern is being flagged at the get-go.

So I'm wondering if it's possible that more than one component is used to validate the OEM license key. The motherboard is a definite. If the hard drive was changed, would that be an issue?