Rubbing alcohol (70% or higher) and paper towel gets the job done.
Re-seating the HSF may not work (for long) since the plastic frame and pins may have deformed over time and may no longer be able to apply sufficient contact force. My stock LGA775 HSF lasted for about three years until this happened and re-applying with fresh paste helped for less than two weeks each time.
While something like the Hyper 212+/212EVO may be somewhat of a PITA to install if your case does not have a rear-access cut-out for HSF mounting plates, it is the simplest way to make sure you'll never have to worry about plastic pins/frame again.
All you need is 70 or 90 percent rubbing alcohol and a non lint cloth coffee filters work great. Take a dry coffee filter and wip off as much of the junk as possible. After that moisten a new coffee filter with rubbing alcohol. Keep repeating until the coffee filter(s) come out clean. Change coffe filters as you go along and they get really dirty.