You should definitely replace the TIM. To do so, first take some isopropyl alcohol (or acetone, it works just as well) and soak a Q-Tip with it. Then rub it wagainst both the CPU metal plate and the Heatsink to remove any trace of the old TIM. Then apply new one. I really recommend IC Diamond 24 over Artic Silver 5, it performs much better (5-7 degrees lower with IC24).
You can buy it here : http://www.ncixus.com/products/44155/IC24/Innovation%20Cooling/
And here is the procedure to apply it : http://www.innovationcooling.com/applicationinstructions.htm
Also, if you've overclocked you CPU, I'd really recommend upgrading your cooler. The stock one simply isn't good enough. For the top of the line cooler, you could go with a Noctua NH-D14 or the Corsair H70.
You can also take a look here to find reviews of CPU coolers : http://www.frostytech.com/top5heatsinks.cfm
Hope this helped,