If a new battery doesn't cure it, then here's how I've fixed this issue.
1. Upgrade the power supply. It floored some owners that an aging power supply may not meet a minimum voltage rise time on a supply leg and could corrupt the CMOS settings or real time clock when it's powered up. This also can be a cold only issue and only by swapping in a 100 more Watt supply and giving it a few days may tell if that's it. Cheap.
2. Replace the motherboard. It is possible that this 5 plus year system has developed a board fault.
Each morning when I start my Coumputer it will always ask me to set the CMOS time and this I will do and click on ''save and exit''. I ve changed the CMOS battery twice. I ve updated the computer time with the OS and the internet as well. I have exchanged the memory with another, all in vain. When I start the computer the next day I will always get the above message. Thanx.... Nd
Intel Pentium 111, 600Mhz Cpu on a tatung motherboard, 128MB mem, using XP pro.