Yes, very strange.
Can you run it for hours and hours on end without a problem? It only happens after you power down? I wonder if the PSU isn't overheating after shutting off or something. Narrow it down by removing every unecessary peice that you need to POST (all but one stick of RAM, HDDs, CD, any expansion cards except for video card), and just for kicks, why not unplug all of your case buttons from the board as well and power it on with a screwdriver (be very careful, but touch the screw driver to the two power-on contacts and that will power on the machine). Make sure none of your case buttons are sticking. I fixed a machine that acted strangely like that and the power button would stick when you pushed it. So we replaced that and it worked. Just use process of elimination.