Windows 7: Intel 2600k Overheating

When you over clock the memory you are over heating the cpu because the memory controler is onboard the cpu.
Yes jacking up the settings on the ram is concidered overclocking.
Here is Intels specs.
http://ark.intel.com/products/52214/

Can you provide an example of a Sandy Bridge Socket 1155 Extreme Edition CPU?

I'm skeptical.

While clearly DDR3-2133 is outside the Intel specs, how much additional power is dissipated in the CPU? (I have no idea.)

Simple enough to test. Revert to the default settings, which will run the RAM at DDR3-1333.

Funnily enough, i reverted to automatic settings ( 1333 ) and the CPU still overheats when under stress (80C)

No two computers are the same. Most certainly no two cpu's are the same. Applies and Oranges.
If you are using Prime 95 100% torture test at 80 C that IMHO is okay. Your chances of working your computer that hard under normal use are slim. That doesn't mean that better cooling wouldn't help. Keeping in mind that no two systems are the same. When I clock my computer a lot I gain about 10c in temp over stock (default) with 100% load to about 80 to 82C. I'm at default now because the ambient temps are very hot 32-33C. No one can tell every thing over a Forum because your computer is where you are and were not. Use your computer as you would normally and monitor your temps. If you want better temps, my best guess would be better cpu cooling. Other than fun I really haven't seen any advantage overclocking today's computers.

Not good AlexRD.
Be bold try the thermal paste solution. You don't need to remove the CPU chip just the heatsink fan. Just be patient and work slowly.

To add: try to get the two surfaces totally clean as possible. Small particles such as lint will reduce the heat transfer.

With a modern copper core heatsink (which is oem with the chip) the heat shouldn't even really be that bad if no thermal compound was used at all.

Alright, i'll first try the thermal paste solution today, then if it doesn't work i'll try an aftermarket cooler.

Will any paste do? Or is there a specific brand i should be looking out for?

Their are many types and brands to read reviews. Like in post # 3, the one that has always worked for me is Artic Silver.
http://www.arcticsilver.com/as5.htm
Their are some that try many and then test. If you want to keep taking your cooler on and off for testing different ones, it's a pain. It's very important to apply thermal compound properly. To much compound will raise the temps.

The truth of the matter is I don't think the brand of thermal compound is nearly so important as we make certain there is some there.

That chip shouldn't be hitting those temps especially not now that we've even reduced his ram to speed.