Easiest first, reset OC to default and see what happens. If you get much better temps, just OC a little more "gracefully", perhaps (If I remember correctly, increasing voltage creates a decent amount of heat. And I read that stock voltage is roughly 1.365, so just for a 400 MHz increase is that increase in voltage necessary?). If it's just as bad, definitely repaste (How often does one repaste? I don't know, but don't go cheap).
Even if it runs cooler with a more conservative OC, try repasting anyways, when was the CPU put in the machine?