|Have the batteries tested to make sure you aren't purchasing old batteries.|
Make sure that you are installing the battery in the proper direction, not up side down (look for the + sign, do not assume it is typical to ordinary batteries).
Are you powering off the power supply or power strip? CMOS batteries generally last many years if the computer stays plugged all of the time but runs down much sooner if the power is completely removed on a regular basis. In fact, the COS settings probably should stay even without the battery if the machine is getting a trickle of power from the power supply all of the time.
If the battery is good, in the right direction, and fully inserted, then the motherboard is probably bad.
You have to be a little bit crazy to keep you from going insane.