Stock Base Clock for the 4790K is 4.0GHz, and while under a 100% workload, Turbo Boost is 4.4GHz. A feature called "Speed Step" causes the clock speed to decrease to as little as 800MHz at dead idle, and increase to Base Clock or Turbo Boost, depending on how much workload is on the processor. What you've described is normal and expected behavior.
• We need to know what your ambient (room) temperature is. It can be a HUGE variable, so it matters.
The "standard" for normal room temperature is 22°C or 72°F. All computer temperatures increase and decrease with ambient temperature. For each 1°C (1.8°F) your room temperature increases, so does your Core temperatures, whether at idle or 100% workload.
Also, if you're going to check idle temperatures, then as Darkbreeze has already pointed out, it needs to be at dead dle, Partial workloads are very difficult to evaluate and compare.
We always need three points of reference; ambient temperature, 100% workload and dead idle, which means just 1 or 2% CPU Utilization in Windows Task Manager. We know that anything else you do with your computer will be somewhere between idle and 100% workload, which really doesn't matter. 100% workload is the most important reference point, which will reveal your hardware's thermal performance.
• You need to run Prime95 v26.6 Small FFT's again to check Core temperatures at 100% workload to find out if you actually corrected the problem with your processor reaching "Throttle" temperature at 100°C, which is much too hot. Please post another screenshot of those results.
• When you removed the cooler, do you remember if the spread pattern of the thermal compound was evenly distributed on the the surfaces of the CPU and cooler?
• Do you remember if the bottom of the cooler was copper in the center, or if it was all aluminum?