Se dice que 1 vez al año pero si la pasta térmica que usas es de calidad puedes tirar casi 2 años para el CPU, para la GPU es preferible aguantar hasta que termine la garantía, porqué la gran mayoría de marcas no te permite cambiarle la pasta térmica.
Hacerlo antes de tiempo no es malo pero dejarlo demasiado tiempo si que lo puede ser.
Lo de notarse en el tema de temperaturas, no deberías de notarlo si no hace falta. Eso significa que la pasta antigua estaba bien aún.
Cuando le notas la diferencia es porqué ya la tenías muy reseca, y lo notarás al abrirlo, porqué no estará viscosa, quedará dura.