No one this has happened? Give at least somebody a theory that maybe?
The problem appeared immediately after cleaning and changing the thermal paste.
If this happened when you cleaned your thermal paste its because you pulled too hard when seperating heatsink from GPU chip and ended up either cracking the GPU chip (micro crack) or you cracked some of the solder under the GPU. So try the oven trick method.
In the future, don't change thermal paste, it won't improve temps and you will only risk damaging it.