New
#11
It's not that hard to remove a mobo. Just make sure that you ground yourself good. Often, cases will have an access panel or hole in the motherboard's back panel to allow you to put bolts through the motherboard to mount a cooler. That way you don't have to remove the motherboard. Before you give up on the idea, check to see if your case has such an access point.
And the thermal paste would be a good investment, no matter what you do. By the sound of things, your paste is pretty old, and is probably not doing the job well anymore. New paste will definitely help, and AS 5 is the cream of the crop IMHO.