Its not the P4 that has an overheat protection but the motherboard. You will usually find it in the BOS settings. The fact that you plugged it in when it was on the mains, although it was switched off it could have burned something. That is very rare, but not impossible. You see if you plug in a PSU and switch it on, then off, the capacitors still maintain some voltage (which is quite a lot!) and enough to cause damage. Good quality PSU's have bleeding resistors for that reason to eliminate that voltage as quick as possible.
Now if you took the board out and tried it there, and still no go, the last thing you could try is check in the BIOS to see if everything is alright there. If so, which i suspect, since you didn't mention changing anything there, then either connect your fans on the molex conenctors or get a new motherboard to try out. This one sounds faulty.