It seems like your registry is corrupted. I had the same problem with Heroes 4; it somehow keeps trying to leave its traces behind. Try installing all parts of Heroes 4 one after another. At some point, you'll get an error saying it can't be installed, but instead, it will offer to uninstall it. Uninstall it, and it will disappear from the list of programs. Then, reinstall it, and everything should work. At least, that's how I dealt with the same problem.