I also read about people whose pulled the CPU out along with the Stock Cooler b/c the paste was really sticky.
This is very unlikely to happen, as the cpu is locked and held firmly in a processor socket in the motherboard.. Its not that EASY to pull out the processor form the socket without unlocking/opening the socket... After all its a thermal paste, not a Super Glue!
Besides the paste that is pre-applied on the intel heats sink easily comes off without much of a hassle:)
I read quite a few people who damaged their mobo during removal because the push-pin was stuck.
The mobo will be damaged "if and only" an excessive pressure is applied on it.. Please Do not wrestle with the mobo :P
A gentle touch will make things easy for you:)