This usually happens when Windows Installer no longer has access to the original MSI used for installing the product. It uses the original MSI file to figure out which files need to be removed before the new install can occur.
Since the new MSI is not the same as the original MSI Windows Installer will not accept it as a 'valid' package.
Repairing the installation
Using the MSI for the version already installed (please contact technical support if you no longer have it) try the Repair option to fix the installation.

Then try to uninstall it manually again. If that doesn't work...
Repairing using Microsoft's FixIt
Click the 'Run now' link on the following Microsoft page:
Fix problems with programs that can't be installed or uninstalled
Why did it happen?
'Cleaner' type products can sometimes be overly aggressive and delete the MSI databases that Microsoft Installer saves for future reference.
What is an MSI file?
An MSI file is a database of information that can be used by the Microsoft Installer to install/update/remove software in Windows. More information on MSI files can be found here:
https://docs.microsoft.com/en-us/windows/desktop/msi/installation-package