I had this same problem once on an older computer, and if I remember right, I fixed it by changing the battery. Have you tried that? Seemed like because the battery was dying, there was something that wasn't getting stored right when the computer was shut down, and by replacing the battery, that fixed it.