500watt is enough in my opinion. Its not a heat problem, heat problems don't occur within a couple of seconds of booting up. And if it was then the computer would worsen as the computer stayed on, and not just intermittently fail at loadup.
Perhaps corrupt boot partition? I don't have a lot experience with this kind of problem; so maybe someone else who has had experience recognizing and repairing these kind of problems could offer some input.
I don't know if a boot corruption would cause a complete shut off