config data for product is corrupt

Windows Installer: The configuration data for this product is corrupt. It does this on a particular software program after trying to completely uninstall an Infoconnect software program by also deleting references from the registry. We've reinstalled Windows Installer, etc. I failed to back up the registry. I know Windows Installer works, because it will install other programs. The program I'm trying to install is an exe on the network.