I recently had a client whose Toshiba A205 laptop had a hard drive failure. After replacing the hard drive and running a system restore from the DVDs, Windows Vista would not accept the system key, regardless if the laptop was hooked up to the internet or not. It just kept saying that the system key appeared to be invalid.
After doing some research, I found KB articles from Microsoft which talked about the need to have Service Pack 1 (SP1) installed in similar cases. Sure enough, once SP1 was installed and the system was rebooted, Windows accepted the system key and the system was validated.
I’m also guessing that this probably only applies to restore media that may have been issued prior to SP1. For example, I know that if you purchase replacement restore media from HP, they include many updates that have been released since the system was first released.
I’m hopeful that Microsoft has corrected this problem in Windows 7 so that a fresh install doesn’t require consumers to hire a computer technican to complete a system restore.