It's been quite a while now, but I don't remember them being stuck on with anything - just the four screws I mention in the article, and the gentle adhesion of the thermal paste (although the original stuff on mine set hard it came off easily enough.)
Of course it's entirely possible that AW manufacture differently to Evesham, and have started using much stronger thermal goop (I wouldn't expect them to use thermal epoxy given the need to remove the heatsink to get at certain components)
when i applied as5 on mine, i can remember the heat sink quite firmly affixed to gpu's after removing the screws also. i used a flat head screwdriver as a lever to pry it loose from one end (very carefully, holding my breath ) and then it came off easily after that.
I had the same problem as my CPU was firmly stuck to the heatsink and I had to pry it loose to apply some AS5. However after applying AS5 I've been seeing temps maxing about after hours of gaming near 74 max for my cpu and nothing greater than 70 for my gpu's with SLI enabled. I've had a lot better time gaming for the past 2 months since doing so.
I ran 3DMark05 three runs in a row to monitor temps. I found that it never went over 72c with the original alienware thermal paste. I just wanted to toss that in for anyone wondering what the differnce was. I own a m9700 with dual 512bg 7900gs'.