What I am thinking is that maybe you had a virus that is a fake copy of Baidu. Since you said that you never installed this yourself, I believe that you probably got infected with malware. Since it was killing the revo uninstaller an ccleaner process and doing everything that it could to prevent you from uninstalling it, I think that it is an infection as opposed to a genuine copy of Baidu antivirus. I found a tool on cnet that is designed to remove this adware. Perhaps this would have been the best option for you:
Code:
http://download.cnet.com/Adware-Baidu-Removal-Tool/3000-8022_4-75532472.html
If it were a genuine copy of this antivirus, I think it is a terrible practice to make a software that unremovable from the system. As for the Baidu antivirus, it seems to have decent reviews on cnet, so the genuine copy from the official website is not a virus itself. I hope that everything is back to normal for you now.