Clean off as much as you can, you lose cooling efficiency by leaving old thermal paste in.
Think of it this way, the whole point of thermal paste is to fill the gaps between the CPU lid and heatsink, by leaving old thermal paste in you create artificial gaps that degrade your thermal conductivity.
So better take another 30 minutes of annoying work, but get rid of the old thermal paste.