It sounds like your operating system has a problem with handling MSI installs/uninstalls. The most reliable solution would be a rebuild of the operating system, but as an interim measure, you should try running MSIZAP, which is a tool Microsoft provided that clears up the remnants of a specific MSI installation. Use with care, but it can solve most MSI issues with a specific app.