I tried spreading the paste, it didn't help much, just shaved 3 degrees at idle (ambient also dropped so that might be the cause of the change), no change during load.
I also saw that the thermal paste didn't have a uniform color, some places it was dark some places light, so I am guessing its the thermal paste that is the problem