If you removed the heat sink, you need new paste simple as that.
The purpose of the paste is because the metal of the chip and the metal of the heat sink are not a flawlessly perfect smooth surface. The paste fills in these tiny gaps and allows proper heat transfer. Once you remove the hetsink that precision filling in of those holes is gone and you will never fit it back in the precise location it was in, not to mention the paste will harden over time.