If you are just using the stock fan and heatsink, and it is installed correctly, I would start looking at aftermarket coolers.
Look at Arctic Cooling, either the Freezer Pro 7 (http://www.newegg.com/Product/Product.aspx?Item=N82E16835186134) or their Freezer 13 (http://www.newegg.com/Product/Product.aspx?Item=N82E16835186039). CoolerMaster and some others also makes some good ones.
Here is th eWarranty info
Not getting the heat sink installed correctly could be considered Voiding the warranty, but I don't see that use of any approved heat sinl is an issue.
Jeremy Wolford wrote:
Don't aftermarket coolers void the warranty, though?
No they do not. The only way they could void the warranty is if they did not cool properly and destroyed the CPU. That is not likely to happen as the CPU will shut itself down before that could happen.
For cooling, the coolers I mentioned are far superior to the OE cooler. By a long shot. OE is adequite, but the AM ones to a superb job. I am running the Freezer 13 on an I7 860, and the fan never needs to go above minimum speed, even when I am working with videos.
As an example on mine, it runs at 40c at idle with the fan at minimum (889rpm) speed. When using the IDCC stress test for 10 minutes, the max temp is 51c with the fan still at minimum. Not even close to max temp.