Product Key Not Valid

A while back I moved my Gateway machine from Vista Home Premium x32 to Win 7 Home Premium x64.
The Win 7 OS was purchased from a well known software distribution outlet to save money, and was a Dell OEM x64 bit version.
The clean install went Ok, but the product key included with the disc would not validate. I called the vendor and they provided a new product key, which did validate.
About seven months went by with no problems, then after the second to last MS update, I received an error after booting stating my copy of windows was not valid.

Again I contacted the vender, and they supplied a third product key, but told me I might have to validate by phone. This didn't work, the third key they had given me was an invalid key as well!
I ended up with MS tech support and after forty five minutes later and granting them control of my PC, the tech provided a working product key, but was reluctant to give me the key!
If I call the vender, I'm sure they will supply another key, but now I'm using a MS supplied key that I don't have access to. What do I do now?
Thanks for any advice!
N2

Download and install Belarc. It carries out a full audit of your system and displays the results in a web page format.

The information should also include the product keys and serial numbers for any software you have installed.

At least now Microsoft can't refuse to validate an operating system that THEY provided the product key for.

If this is Upgrade version and you clean installed, then you may need to do one of the workarounds given here to activate Upgrade version on a clean or wiped HD: Clean Install with a Upgrade Windows 7 Version

What is the name of this software dealer that keeps providing new keys for ones which don't work. This is not typical retail behavior as the boxes should be sold sealed with a COA sticker guaranteeing authenticity of each by MS.

The disc I have is a Full Version, an OEM Dell disc. Although it didn't arrive boxed or sealed, it was accompanied with the COA sticker.
I reformatted the drive, originally equipped with Windows Vista HP, and then installed the Win7 HP.
I'm not sure it's proper to list the company's name on this post, but they have been around for a while.
N2

I don't think a retail software company should be selling Dell OEM disks. These are meant for Dell to distribute. What did MS say about this?

The normal procedure if you buy a legitimate retail disk with key on COA and it fails to activate is that MS Customer Service validates the key then opens a Support case to get it activated one way or another. I would go back to MS Customer Service and explain the situation, including exactly what disk you were sold, and if they will pass validation on the key they will get it activated according to policy.

If not, I would insist your vendor sell you a sealed boxed retail copy of Win7 which does not include Dell OEM disks that I have ever seen. Maybe someone else knows if this is legit.

As stated in my opening post, the problem so far, has been rectified, as Microsoft has issued a verified registration key. I doubt the vender would have directed me to call Microsoft, in the event of any problem with the new registration key they were sending me, If they were worried about their software business practices.

When I called the vender, they explained they had been having problems with some of their Registration keys verifying automatically since a recent Windows update, and that I would most likely have to register by phone.
I don't know if you only get so many chances to "Auto Verify?" (by typing registration key in) and verifying over the web, but after several attempts with no luck, and after trying to verify the last key received, by phone verification, my choice of options narrowed on the verification wizard and I had no choice but to call Microsoft for help with my verification.

A Microsoft Tech Opened a case file and over the course of forty five minutes, tried to verify the new key I received as well as the old key that had been working before the updates with no luck. I then ask if I needed to re contact my vender to resolve this problem and was put on hold, a few minutes later the tech came back on the line and told me to stand by while he then typed a working registration key into my PC and tested that it verified correctly on my machine! That did the trick and he closed the session.

When I ask him for the registration key, he told me I could contact Microsoft anytime for help with verification. I explained that in the event I had to go through this again, I would really rather try to re verify myself first rather than spend an hour on the phone, he reluctantly gave the number, but I somehow missed the last character! My thoughts are, since this key was supplied by Microsoft, If I can locate it within the machine, I'm good.
I have not had time to try "Magical Jelly Bean" yet, but I'm hoping one of these programs works, as calls to Microsoft can be trying on one patience!!
N2