So when I apply the paste, should I clean oft both the cooling plate as well as CPU and fully reapply? Also, any cleaning tips?
Yep, make sure both the CPU and HSF are completely clean. The easiest and best way to do it is with isopropyl alcohol on a lint free cloth, but a damp paper towel will work in a pinch. Just watch out for lint.
Also: how confident are you that this is what is causing the overheating? (The gaps that is...) Seems to make sense that the old paste was creating gaps, but I sad not sure if paste hardens or stays malleable...you live you learn, Lol.
Pretty confident, actually. It doesn't matter if the paste is old or new, it's like you said, that the tiny air pockets that are created when you use what was there before, will create and uneven surface.