Talking hyperthetically, suppose I had a non-legitimate version of Windows XP, but I have now obtained a legitimate key (it belonged to an old computer that has now been trashed). How can I make the version legitimate without having to reinstall?
For the solution given by whitequark to work, the two XP versions must be of the same kind, since one cannot activate an non-OEM version with OEM serial.
If the versions don't match, the solution will be to reinstall XP using the boot CD of the thrashed computer (if you still have it), or search elsewhere. It is not illegal to download via torrent a copy of a software that you own legally.
However, if the thrashed computer had an OEM version, then the license is "hardwired" to the computer and cannot be used on another, so the activation may not work.
This article describes how to de-activate your system. Then you can just launch the standard activation process again.