Removing the battery does not always clear the CMOS memory. Do it properly and use the clear CMOS link with the power lead DISCONECTED. This problem can also be caused by faulty memory.
I disagree I have had motherboards where removing the battery does NOT clear the CMOS memory due to the capacitive charge on the chip being enough to power the memory for many days, even shorting the battery terminals will not clear the memory due to diode action.
The manufactures provide the clear CMOS link for a reason.