Things to check, if you haven't already:

1. Check to make sure all fans are working properly. You could try something like SpeedFan to see what temperatures are detected also. Make sure there is no dust buildup on components.

2. Remove and reinsert the video card. Check for corrosion on the slot connector contacts. If no improvement, try a different slot on the motherboard, assuming one is available.

I assume that you have the stock HP power supply in that computer. Post the wattage rating.