The video card only has 1 power connector, and it needs a minimum PSU of 450w with a minimum 12v current rating of 24amps.
Now heres where I'm not sure about, each 12v rail is rated at 18amps, but I don't use that when fiquring if its enough, I use the 48 available amps right which means it should be enough?
Nice job troubleshooting too. That under-underclocking test is pointing at a power problem.
The GTS 250 is getting up to 75watts (6.25Amps) through the PCI-e slot and up to another 75watts through the PCI-e 6pin power adapter which should be plenty. Either the power supply is having a problem or the PCI-e slot might be having a problem delivering getting the power to the card.
What motherboard are you using? We can check and see if there is any history of this type of PCI-e slot problem.
If not your PSU is the prime suspect.