Hi,
The Product Key has to belong to that machine, as you can not transfer OEM Licenses from one Compute to another.
IF it is is an OEM Product Key that is on COA Sticker on the underside of that Toshiba Laptop that you have reinstalled Vista on, phone Activation may be required.
If it does require phone Activation, do not follow the Auto Prompts, but hold on for a real person to explain to as to what has been done for re-installation purposes.
"How to Activate Vista Normally and by Phone Activation"
http://www.vistax64.com/tutorials/84488-activate-vista-phone.html
Cheers.