PC won't power on, sometimes, when I press power button

I have a system that was running fine for years but now sometimes when I press the power button the PC won't turn ON. When it's on it runs just fine, no BSOD and no crashes or errors.
Sometimes I have to remove the power cable for several minutes for the system to turn on.
I have run Prime95 for 24 hours (on both cores) and Memtest86+ for 15 hours (several passes) and no one error.
I tried two 600W power supplies (Antec and Thermaltake) that are working fine on other systems

Any ideas? :(

Specs
MSI K9N Platinum (7250)
G.Skill 4GB DDR2
AMD Athlon 64 X2 4200+ Windsor 2.2GHz
ATI Radeon AIW X1300 256MB 128-bit
Sound Blaster Audigy 2 ZS
Microsoft Windows 7 64-bit SP1
Two seagate HDD (320GB & 1TB)
 

foverosiv

Distinguished
Jul 18, 2011
179
0
18,710
perhaps your case? the wires connecting to the power button might be the problem. try to power up the computer without using the case by pressing the power button on the mother board or if your board doesn't have the power button, try to shorting out the power pins on the motherboard, if you can continue to do that for several time, then its probably the bad wires from the case.