Bastaklis,
It's highly likely that both stock coolers had coincidentally popped a push-pin loose from their respective motherboards, which is a very common problem. A loose push-pin causes poor contact pressure between the cooler and the CPU, resulting in high temperatures in BIOS, as well as in Windows at idle, and especially when approaching 100% workload.
The reason temperatures didn't improve after you replaced the thermal compound is that the same problematic push-pins on both stock coolers that originally caused the temperature problems on both computers again eluded detection ... you just simply didn't notice the problem. You're certainly not the first to unknowingly have your efforts thwarted by Intel's push-pins.
Nevertheless, you can troubleshoot this problem by pushing firmly on each corner of the cooler for about 30 seconds while watching your load temperatures. When you see a significant temperature drop, you've found the loose push-pin.
The push-pins can be deceivingly tricky to get them fully inserted through the motherboard and properly latched.
(1) To re-seat a single loose push-pin, rotate the latch mechanism in the direction of the arrow counterclockwise 90° then retract the pin by pulling upward. Rotate the latch clockwise 90° to reset the pin, but do NOT push on the latch yet.
(2) To get the pin fully inserted through the motherboard, push only on the leg, NOT on the top of the latch.
(3) While holding the leg firmly against the motherboard with one hand, you can now push on the top of the latch with your other hand until the latch clicks.
(4) If you're re-seating the entire cooler, then be sure to latch the pins across from one another, rather than next to one another. Use an "X" pattern, so as to apply even pressure during installation.
Intel Stock Cooler Installation -
https://www.youtube.com/watch?v=5qczGR4KMnY
Concerning delidding, 2nd Generation Sandy Bridge CPU's are soldered, so there's nothing to be gained by attempting to delid a 2500K, even if you managed not to destroy it during the process. In contrast, the 4770K would greatly benefit from being delidded. As Intel's TIM degrades over time, some 3rd and 4th Generation 22 nanometer processors, (launched 2012 through 2014), may no longer cool as well as when new. Many users with processors such as yours have noticed their Core temperatures are higher than they originally were.
You might want to read this Sticky:
Intel Temperature Guide -
http://www.tomshardware.com/forum/id-1800828/intel-temperature-guide.html
See Section 9 - The TIM Problem.
CT