have you tried a minimal setup. use the least amount objects installed on the pc. if the cmos battery is giving issues your motherboard may be the issue but running with that shouldnt be your first idea. anothe thought if you removed the cpu heatsink have you replaced the thermal compound and if conductive compound was used ensuring that none of the paste has come in contact with the board. if the heasink was removed the reinstallation of the heatsink was proper. sometimes having another set of eyes lookover your work may yeild clues as to how things may be going wrong. your issue is most likely hardware. troubleshoot steps are below.
i anticipate that when you cleaned everything you removed mobo from its position. if that is the case make sure your not grounding out the mobo at any point. im certain ypu did that already.
remove as many components as you can like graphics cards. networking cards, all drives except you target harddrive and media. it is preferred to use onboard graphics. if the problem persists consider removing the harddrive and use a bootable linux dvd or usb. at this point we have ignored the cmos clock and battery issue in hopes that the problem has fixed itself.
seeing as you have access to the bios try to reflash it to ensure it is the most updated and not corrupted.
good luck buddy i hope i didnt post what you have already done.