CPU overheating problem: Thermal paste or something else?

Bill's right. Anytime you remove the heatsink from the processor, even if you just applied thermal compound 5 minutes ago, you must remove the old thermal compound and apply new. Any voids or air pockets will hold heat and become hot spots. A high purity isopropyl alcohol of 90% or better and coffee filters works well for the task.