Taking in consideration that your notebook is at least over 1 year old, and full of dust inside, the replacement of the thermal paste will cut down the overheating of the notebook thus preventing it from heat-related shutdowns.
That we can be sure to be out of the way. Other issues, just have to go one by one and see.
cheers ...