You May be a Victim of Software etc

I have a Toshiba Tecra With Xp Pro and a legal activated coa on the base. Since April I have a message at the bottom of the screen that says I may be a victim of software counterfeiting. This copy of windows did not pass genuine windows validation
I have done nothing to the pc for months except use it on Ebay for browsing
Microsoft say it is nothing to do with them and the only way to get rid of it is to upgrade at a cost of £109

Surely this is blackmail. I have no malware or viruses. My first call to Microsoft was cut off after 20 minutes and the second to the complaints dept in India resulted in my being told there is nothing they can do as support is withdrawn and I should phone Toshiba in case they have done something to the pc while I have been online

Any ideas please.
Really hope you get this sorted out. However, may I suggest that, since you will no-longer be receiving any updates from M$, you may want to turn off automatic updates as well?

Depending upon what you use your computer for, there may well be a number of services you no-longer need. On mine, I have turned off 72 services, resulting in the same features, but a much faster, more stable machine.

As I siad in another thread, not for everyone, but Automatic Updates are definitely not worth keeping on