This happened to me with a P4 1.8Ghz CPU.
I didn't think of heat so I tried to pry, not a great idea as I almost broke it.
Then I just got pissed and got a hammer and screwdriver and smashed the side of the CPU pretty hard on all 4 sides about 5 times each. On the last hit, it came off. Then I had to soak the Heatsink and CPU for about a day to get it clean.
Very big hassle all for nothing as the computer won't accept XP SP2.