Which product key?
The key for the OEM installed version may not be the same as the key
shown on the case sticker. The OEM restore disk may not need a key,
have it's own key, or use the key on the case.
(Depends on how the OEM did things.)
Sometimes, the OEM installed version was a "generic" build version used
by the OEM. The sticker may have a different key to be used with a user
reinstall.
I used the Product Key on the box and it worked first time I tried - but
wanted to re-istall it again but wouldn't accept the Product key so I have
left it