Hmm.... I thought you could change a key in XP quite easily? As long as it isn't activated you could install with one key, find the old one, restore the hardware hash files and then reactivate if necessary?

This page covers backing up the wba.dbl files, there is a tool out there which helps you change the installation key (from which the product key is derived), however I'm not sure how to get a key from a non-active installation, it must be possible though.

edit: Here is one which seems to do everything required, but only on a running system. Is there any way you can get the old installation running again?

Gareth