Well, since dndhatcher said that stock fans aren't good enough for overclocking, I decided to go buy an aftermarket fan and bought the Corsair A50. I applied the thermal paste by putting a dab in the middle and put the heatsink on top of it. Already in Prime95 I'm noticing a huge difference: High under load is 81 C, almost 20 C lower than before with the stock fan. The idle temperatures don't seem to have changed that much, but I'm definitely much happier with the thought that it shouldn't get too hot now.
Edit: Actually, the idle temperatures have dropped a good amount too. I finally saw temps that were in the high 30s.