I have been running a i7 2600k for the last 2 years mostly O/C'd at 4.2 gHz and have not ran into any temperature issues and or even a single crash with the same setup as I have described above. My cpu idles at ~38C and tops out somewhere near 55C even under stress testing. Also I use RealTemp to capture the temperature.
Picking a CPU cooler really doesn't take much effort. It's a little bit of physics. The more surface area the heat sink has and the better the airflow will allow for great temperatures. Just make sure it will fit in your case and motherboard so that it doesn't snag the memory or other components. Something like this will do great. It's $30 shipped after rebate and it does a really good job:
http://www.newegg.com/Product/Product.aspx?Item=N82E16835103099&cm_re=heatsink-_-35-103-099-_-Product
However do not put off the most important part in a CPU cooler. Like many have suggested in this post, the method of installation is key. You almost have to be OCD about the process or you will get it wrong and end up hurting the CPU more than helping it.
The stock cooler does NOT help you understand this process because it seems so simple, however if you are overclocking you want to do some research on this topic. I literally spend 2 hours watching YouTube videos to see every expert's opinion. The fact is you have to get the contact points 100% clean and the CPU paste needs to be applied in the correct amount. a little too much or too little and you will end up hurting the temperature then helping it. So to help you understand here's my steps on how to install a CPU cooler:
1. Get a high concentrate bottle of rubbing alcohol. Something like this will do:
http://www.walgreens.com/store/c/walgreens-isopropyl-alcohol-first-aid-antiseptic/ID=prod6056576-product?ext=gooMedicines_ampersand_Treatments_PLA_Antibiotics_ampersand_Antiseptics_prod6056576_pla&adtype=pla&kpid=sku6052670&sst=1262ea15-37b9-6368-4b34-000055f83fc5&kpid=sku6052670
2. Use cotton wipes and q tips and clean the heck out of them. I mean like lab clean.Also make sure there is no residue anywhere on the motherboard or socket
3. Apply the proper amount of cpu paste. I prefer making an X shape with the thermal paste and using the contact pressure from the cooler and the cpu to spread the paste without air bubbles. The total amount of paste should be no more than a dime swipe dot. Like making pancakes try to use the amount of paste that equates to a dime size pancake.
4. make sure the cooler is installed 100% correctly. I find after market cpu coolers easier to install properly than the stock twist on types because you get to screw mount the cooler on the motherboard. Make the contact tight but not too tight that it cracks your motherboard. Most importantly make sure nothing gets dirty and do not touch any of the contacts with your dirty fingers. Use gloves or use plastic wrap to keep your oily fingers off any of the contact points and also keep off the thermal paste.
5. So for thermal paste I prefer the non metallic ones. Even though benchmarks show a slight benefit when using metallic pastes the risk of getting a drop on your motherboard and fry the thing is too great for me to be comfortable with. I would suggest something like this. It has great performance and can't fry your motherboard:
http://www.newegg.com/Product/Product.aspx?Item=N82E16835186020&cm_re=thermal_paste-_-35-186-020-_-Product