Sometimes Arduino board does not start up...

I am having a strange problem. Every now and then when I cycle the power on the board it does not start up. At first I thought that it may be the caps on the board that have not discharged totally before applying power and thus the counter does not reset so when power is applied the counter starts where it left off and enters a random undesired state. However even if I leave the power off for 10-15 sec it still happens every now and then (about 1 in 6 times). Sometimes this happens even though it is the first time I am turning on the board after it being off for hours... Once it enters this state I can sometimes get it to start up again by holding the reset button for something like 20 sec, disconnecting power and re-applying it ... but this does not always resolve the issue.

I am always able to get the board back to a working state by re-programming it.

I also thought that it may be my code, but this even happens with the simple flashing LED example. The same thing happens with 3 different boards.

It is weird because there is nothing strange about the arduino circuit... could it be related to the bootloader?

I am using a 12V power suppply (which has about 16V without load) instead of the 9v - but this should be ok too as the regulator can handle up to 35V. The regulator does heat up a bit - but nothing crazy....

Anyone else seeing this? Any ideas?