To get the gunk off the CPU and heatsink, just use isopropyl alcohol. Depends on what type of thermal paste was on before, cos I just found out some crappy stuff they used for my Northbridge cannot be removed totally.
Personally, I think the best is to follow guidelines, which is not to have a heatsink heavier than... 500g? Most heatsink solutions these days are heavier than that, and may cause motherboard problems if not handled properly.
For best HSF (heatsink + fan) solution, I'd get something that comes seperately. As in, the fans come seperately. Off the top of my head, I remember the Hyper48 works pretty well, and cheap too.
After that, just get a huge 80mm-120mm converter, and put on a HUGE 120mm fan, with a decent CFM.
Other people may have other ideas. Watercooling for example, which suddenly I find I have a craving for.