The computer is only 3 years old, does thermal paste have that short of a life?
Depends on the quality of the paste, but yes it could very easily be dead. High end pastes will usually last 5+ years if not run too hot for extended periods.
Follow exploder's instructions. Do a good cleaning job on the machine. You would be surprised how much air flow restriction dust and dirt build-up over 3 years will cause.