You should always replace thermal paste when removing the cooler.
If you do not, you may get air(or dust for that matter) trapped between the cooler and gpu core. This would not be good.
I am not saying that it can not be done, but it is not recommended.