Leave it with the battery out longer, or use the clear cmos jumper (usually near the battery, it's normally a matter of moving it from pins 1 and 2 to pins 2 and 3. Some boards require you to awitch them on while the jumper is in this position, others do not (and probably will not thank you for doing so), check the specific procedure for your machine online/in the manual.
It seems that something held enough charge to keep your old settings, unlikely as that may sound, I've seen machines hang on to settings for much too long with no cmos battery (they should only last a second or two until the CMOS memory loses charge) must be all this modern energy efficient guff.
Anyway, with a full, by-the-book, cmos reset, if the problem persists, it's time to start reseating components.....RAM, then video card, then other cards, and finally as a last resort the CPU (cpu's usually have the weight of 4 elephants on them from their cooler clamps so they tend not to squirm in the sockets like other components....not as much anyway)
