So ruled out are:
-OSX
-RAM
-Battery
If the working after restarting really isn't just a random thing, then i might guess it's something related to the bios, but that would be tough to diagnose.
Other possibilities:
-power supply - perhaps after some warming up it functions better?
-i had a cpu fan on a pc once that didn't fire up on cold start, but did start on restart. this isn't likely because there's no dedicated cpu fan (i don't recall there being one at least), but checking to be sure all fans are functioning or if there is a difference in sound between cold start/restart wouldn't hurt.
-hdd - not terribly likely, but hdds have been know to be very odd. switch it out if you have an alternate.
-graphics or other card - probably not driver related since you reinstalled osx, but if you can switch it out for another why not try
-could always be the logic board or processor itself, but these are last resorts of course
If you troubleshoot and come up with nothing except logic board/processor, you could always put it to sleep instead of shutting it down. I don't remember stats on these models in deep sleep, but power consumption is <10w I thought.
Good luck, these problems are very annoying, but if you find the cause it really is a great feeling.