Constant CMOS problem

I've searched extensively and cannot find anything with precisely the same issue and/or plausible solution.

For the past few days my computer has had trouble booting up properly. Whenever I try to boot up, I will get either 1: an immediate shutdown (Not shut off, it just goes to a blank screen and doesn't do anything) with an LED error code 9.0., or 2: a seemingly normal boot up until it starts reading drives and displays a few lines:
(paraphrasing)
"CMOS checksum error
Warning! System is now in safe mode
Please reset CPU frequency
Press F1 to continue, Del for BIOS menu"

If I go into the BIOS menu, nothing seems out of the ordinary; the time is still kept but all Uguru(Temperature/fan/power monitoring) settings are set to default. If I change anything(or simply save&exit while actually changing nothing) the machine will shut down completely again.

If I hit F1 and continue, it will boot up as normal, loading windows with no problem, but the Uguru program, if you are familiar with it, shows something very interesting:
http://img191.imageshack.us/gal.php?g=uguru1a.jpg

Notice how the program is getting NO information, normally it has settings and information for the CPU/PWM temp, fans, and voltage.

I've tried replacing the CMOS battery (didn't help)
Clearing CMOS using the jumper (didn't help)
Updated the BIOS (didn't help)

I have an idea on the problem, but any other ideas/suggestions would be appreciated before I go doing unnecessary things to this computer.

Thanks for the help. I tried switching out the RAM sticks in numerous ways, but nothing changed. The link seems to suggest things I've already tried: CMOS reset, BIOS update...

I'm thinking the CMOS chip may be corrupt/damaged.

Just a note: in the ~20% chance that I manage to get to the POST screen and I hit F1 to continue to Windows, the machine runs just fine (minus the temp/fan/voltage settings). I can play games, listen to music, basically everything it could do before.

I would like to try that, but with the BIOS staying at default settings, the CD will be read after the hard drive and there is no way for me to change it.

It looks like it must run before Windows loads, so I don't think using the command prompt will work.

Then that's clearly related to POST which is not up to the stage of reading the mbr on HDD before loading the OS.
Since different RAM combination doesn't work and no other components besides a faulty CPU can cause that problem(which is almost impossible), then it's really down to the motherboard itself. You've said updating BIOS doesn't work so something else on the motherboard must've gone wrong. I would RMA it.

I have a P5K-E that does exactly the same thing as yours. But since it's been modified extensively for overclocking(the problem happened out of nowhere and not due to the mods) I could not RMA it.

Given that the board is quite old (2+ years), I doubt they will offer an RMA. Luckily the computer runs fine otherwise, so I hopefully have enough time to get a replacement.