^^ I don't much care for the sealed coolant tubes for several reasons including the fact that *if* they worked, they would only work in specific orientations; i.e., in a this-side-up configuration. Turn it 90 degrees and it may not do anything at all.
DM's comment about thermal paste isn't incorrect, but you have to *really* screw it up to take your CPU to 100C and even then it has sufficient thermal protection built in (since about 2003-2004) to shut down before it causes itself any harm.
Overall you've got it right; if replacing your power supply fixed most of the problem, then the power supply *was* most of the problem. I still rather suspect the fan was pointed in the wrong direction too.
Note that the guy in your video is doing a TERRIBLE job with his thermal paste. What he's really doing is proving that it doesn't make much difference most of the time. If you want to be a perfectionist (not that it will matter) you should be sure to remove *all* residue, apply just enough to spread out over the whole CPU cover and no more, and avoid any "loops" that could result in air bubbles.
But again, it doesn't matter. What you've done is verify that:
1. Your power is correct, sufficient, and clean
2. Air flow through the chassis follows a single unified constant stream (speed matters less than direction)
3. You have enough thermal paste to eliminate air between the CPU and heatsink (that's the only thing that makes more than a couple degrees difference)
4. Your heatsink has enough mass and surface area to collect and dissipate as much energy as is generated by your typical worst-case sustained load without taking your fan out of quiet range.
Now as you get bigger and better heatsinks with bigger and quieter fans, you'll reap the benefits of a quieter PC. Well done.