I have gotten IObit's Uninstaller to remove some stuff, but frankly it seems to be missing a bunch of stuff that is supposedly specializes in. Could be it wasn't properly installed in the first place and that is the reason.
I've used Iobit's uninstaller for a while now and have had no issues with it, so I'm not sure why it seems to be missing stuff. As you said, it could be that it wasn't properly installed to begin with, as in like a proper program, but it could also be that the problem lies with the virus(es). It may be that it/they are not allowing certain items to be detected and/or uninstalled because it/they depend on them.
I recall when my mother got this toolbar and search engine thing that kept hijacking her browser, it took me a few hours to completely rid her machine of it and all its remnants. No matter how many times I uninstalled it using Iobit's uninstaller, the toolbar was there again after a reboot. I had to go through the registry, Program Files, Progam Data in C:, AppData, in her personal folder and the Windows Folder to remove all references to MySearch.
However, there is an easier way now... Junkware Removal Tool. It effectively locates and destroys unwanted files on your PC, so give it a try first, then try Add, Remove Programs to see if is again operational. If not, you could try opening CMD Prompt as administrator and type sfc /scannow, which should restore any Window files that were either missing or corrupt.
Anyway, try that and see how you go. Hopefully it works, but if not you can always repost here to see what else can be done.