System Shuts Down During Boot Up

My PC had become rather slow after it had notched up 5 years of faithful service, a problem that wasn't helped by Norton Antivirus (SystemWorks 2002) becoming ever more bloated and resource hungry. So I decided to wipe and re-format the hard drive and opt for a complete fresh start. I didn't re-install Norton - I opted for the latest free versions of AVG Antivirus, with Spybot Search & Destroy and Lavasoft Ad-aware taking care of all the other nasties. The system is cleaned rigorously and is free of all viruses / nasties.

All went well and my PC returned to its former glory - running faster than Ben Johnson on steroids! However, an annoying problem has recently set in whereby it shuts down during boot-up for no apparent reason. Approximately 2 to 3 seconds after switch on, the whole system shuts down in an instant - just as though someone has pulled the plug. But the power supply is fine as the motherboard LED is still lit. At this point I am unable to restart the system via the on/off button on the front of the tower case. I have to pull the mains plug and wait for about 15 seconds before reconnecting and switching on.

The system will then re-start but goes straight to the BIOS setup screen where it says during the last boot-up, the system hung for an incorrect CPU speed. Yet the correct speed is displayed (1733MHz) so I press F10 to save the settings and the system will then re-boot perfectly.

Having put up with this everyday for 2 weeks, I decided to replace the CMOS battery (which turned out to be OK anyway) and to test the RAM chips with Simm Tester. All were perfect. I also re-set the BIOS to its default settings. More recently, the problem has got worse. It now occurs twice during each boot - once as described above and then again when Windows is about half way through loading. I've also tried a different hard drive but the problem still exists. I can't help but feel I'm now on borrowed time!

One thing I have noticed is that it only occurs when the system is cold. Once it has been running for about 15 minutes, I can shut down and re-start immediately with no problems. This made me wonder if it was an electrical issue, but given I'm not an electrician, I'm a little lost. I have tried inspecting the cables, connections and capacitors but cannot see any apparent external damage.

Can anybody out there please help?

SYSTEM SPECIFICATIONS:
YEAR OF BUILD: MAY 2002
MOTHERBOARD: ASUS A7A266-E
BIOS: ASUS - 42302e31 Award Medallion BIOS v6.0 Award Plug and Play BIOS Extension
CPU: AMD Athlon(TM) XP2100+ 1.7 GHz
RAM: 512MB DDR PC2100
VIDEO: NVIDIA GeForce4 Ti 4400 (Microsoft Corporation) Ver. 6.14
AUDIO: CREATIVE SOUNDBLASTER AUGIGY
HARD DISK: 80GB - 7200rpm
OP SYSTEM: WINDOWS XP SP2
ANTI-VIRUS: AVG (FREE EDITION)
ANTI-SPYWARE: SPYBOT SEARCH & DESTROY
ANTI-ADWARE: AD-AWARE 2007