Take it back to the shop and tell them to give you an original XP disc. If they say no, click here to report them to Microsoft and to the police, as what they have done is illegal. A lot of small shops will install 1 copy of Windows on all their computers to save money. However by law each machine needs a seperate licence. There is a new Windows Update component that downloads onto every computer with a Windows installation that reports if the copy of Windows is fake and this should scare a lot of shops into doing things properly and installing a legal copy of Windows on all machines. Taking it back to the shop and demanding a proper copy and threatening legal action should do the trick.
Sounds like he either bought the computer from a shop that did an illegal installion or he installed a pirate copy himself. You need to get in contact with him and ask him where he bought it from and whether he reinstalled Windows - try not to tell him about it being reported as counterfeit because he could fob you off. If he says he got it from a shop, then find out what shop it was and go to them about it. If he says he installed Windows himself ask him where he got it from. In either case, tell Microsoft about it - if the bloke you bought it from doesn't want the police breaking down his door at 6 am it's his own fault for installing a pirate copy of Windows.
It was a bit of an over reaction unless we've just uncovered a huge piracy ring and this bloke was the leader :-P Anyway the computer should be traced back to where it was bought, especially if there is no sticker on the side with the product key on it.