Somehow, removing the heatsink to clean it seems a bit drastic -- a lot of trouble, and an increase in risk -- let alone the consumption of thermal paste and the time to let new thermal paste reset.
If the problem is "cruft" between the fins, I can't understand why the paint-brush idea won't work. If it is "tarnish", I don't see how tarnish is going to significantly affect heatsink efficiency.