Setup Error - Please Help

I have had office 2003 installed and working on my computer for some time
now, and now when I try to open any of the applications, it asks me to
re-setup. I enter my name and my key code to get a message "You have not
entered a valid key product - please check # on sticker......". I recently
called Microsoft, and they validated the key I am using, but wanted to charge
$50 to help. I denied their help. I paid good $ for their product, and it
should work!

Can anyone help with this matter? The key code is valid!

Thanks.