Doing a recovery using the HP recovery tools will not require a key. If recovery options are gone, because you formatted drive, you would have to contact HP and order a set of disc.
The specifics of OEM keys/ Microsoft keys I'm not positive about but it goes something like this: Using an OEM disc will not require a key during installation. It uses like a universal key that along with something put into the bios automatically activates Windows.
They key inside of Windows will always be different from the key on the sticker for manufactured PC's like Dell, HP.
That's why when you use another installation disc, like a retail DVD it won't activate on its own, and you have to enter key on the sticker and do a ROBO call to Microsoft to activate.
Again, I'm only slightly correct!
Since the key is no longer visible and if you require for installation, because your NOT using an OEM HP disc, HP will force you to buy one of their installation disc, where they key won't be necessary.
I doubt they will just give you a new key but maybe they could look it up.