It seems that compressed air is highly used. That's what I do myself. This time around, I think I'll also use a vaccuum, because we bought a really nice one at Christmas. Cleaning the fans is always a challenge. I try to keep my fans stationary while blasting them with compressed air.
I don't know about removing the fan/heatsink and re-doing the thermal grease. I could handle that with my P4. Even though I have the CoolerMaster JetAir 4, which is massive, the locking mechanism makes it pretty easy to do. I think I'll pass on doing it to my daughter's AMD. That was a real challenge

Keep the tips coming.
Robert