Hi, invariably if the fan is clogged then thermal paste will have degraded.
I believe that the silicone or other compound eventually evaporates or otherwise decomposes and
the result is flaky cooling.
Its also worth checking that the CPU is clean, sometimes they get fingerprints on the core and this can cause no end of problems over time even if it "seems" to work initially.
Usually just clean it with IPA and do the contact area on thermal pipe at the same time.
Also be aware that thermal compound containing silver can cause anomalies with silver migrating into the surrounding areas such as capacitors so you should be cautious and use only a tiny amount.
I once trashed a very expen$ive TV by using it on a HOT (hint: don't do this!)