Try using the Magic jelly bean - ( Download Linkie
) -- It will give you the serial number that is currently in use on the system - then compare that to the sticker to see if it matches. Another option would be to contact the support line of the laptop manufacturer - they will ask you for some info off of the laptop (ie. the readable portion of the sticker and perhaps make\serial number of the laptop etc.) and will usually provide you a new key.
Also many times the key is already included in the recovery disk image that was provided with the system (or hidden partition on the HDD) so resetting it to factory state will normally also copy the key onto the new HDD upon reinstallation from the recovery disk.