Key updater not working

We have a computer that was bought from a now-defunct computer reseller that
had an invalid VLK product key on it. We bought new copies of Windows XP
Professional but on this machine, it will not allow me to update the product
key to the legal one. Of course, to simply email MS support would cost us $59
on top of the $145 we paid for the Windows XP Pro we bought. Is there some
way other than through this downloadable tool to update the product key to
our legal key?
Thanks