Supondo que o próprio sistema de resfriamento (ventiladores, bombas, etc.) esteja funcionando normalmente, isso soa como uma transferência de calor insuficiente da CPU atual para o ar circundante.
A maneira mais comum que pode acontecer é se a pasta térmica se evaporar por qualquer motivo, e isso pode acontecer se a temperatura da CPU ficar muito alta em algum momento. Também poderia ter sido deslocado, se o sistema tiver sido exposto a estresse físico.
Eu aplicaria a nova pasta térmica primeiro e verificaria se isso ajuda. É barato e é provável que resolva o problema.