well.............you could try still try to find the 'actual' key used on your laptop - i'll pm you
i had a friend with this same problem a few weeks back - he had recorded his install xp key plus had the one on the sticker - he borrowed my xp cd which was the same type of xp but it wouldn't accept either key

I even went round to check he was typing them in correctly! I was going to look in to it but he found the recovery cd so just did a return to a factory image. I did try installing xp in a vm with his keys but got the same result - never got round to trying to nail the problem. I was thinking perhaps my xp cd has sp2 integrated while his laptop originally came with just xp?
At the moment i have a copy of his i386 folder so i'm going to recreate the xp cd that was used to install xp on his laptop the first time round - and see if that works?
If you have access to the hard drive and can copy the i386 folder off you can try recreating the xp cd that was used to install xp on the laptop.
Have you tried MTChandlers repair xp instructions that are in this forum somewhere - dang! think you need the key for that.
If there is a way of calling MS i'd go that route first, sure they'd be ok when you explain the problem