can’t install sp1 or sp2!

I’m not able to update my XP Pro OS because of a problem with authentication on the volume licensing product key, I have the original 25 digit key, but microsoft says that it is not valid! Thus, I cannot update even to sp1, I recently had to re-install XP due to viruses, but I didn’t low level format the hard drive, did I need to? my error message says this: Windows XP Servvice Pack could not install: The product key used to install windows may not be valid. To get more information on why you have recieved this message visit: www.howtotell.com

Can anyone help?
Thanks…
Paul……..