I had exactly the same problem, did almost everything you did but finally found that the BIOS chip (Hardware) had the problem, took the computer for local motherboard repair as it was out of warranty. They flashed the latest BIOS but that didn't help then they did a bios chip level resetting that also didn't work, then they found the circuit to bios chip was faulty which they repaired. Now I don't have this problem. BTW my computer is 11 yrs old.