Renaming the ProductCode is treating the symptoms not the cause. The problem occurs when the uninstaller doesn't remove the dll. The next install will use the dll again and can't remove it on an uninstall event because it's still used by the other program.
These steps hopefully solve the problem:
Install your Software
Open CMD (with admin privileges) and run:
msiexec /x {ProductCode} /L*V "C:\CustomPath\FileName.log"
The ProductCode can be found when hitting F4 on the Setup Project
Open the log file and search for the lines that look something like this:
Disallowing uninstallation of component: {6CEC09F6-9108-7062-A692-2BCBACEE3BD8} since another client exists
Disallowing uninstallation of component: {A0A0FA84-CC0D-C5C4-1F57-169788C4482D} since another client exists
Disallowing uninstallation of component: {XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX} since another client exists
All these components have to be removed from the registry by hand. To do this the GUID (e.g. {6CEC09F6-9108-7062-A692-2BCBACEE3BD8}) first has to be converted into a packed/compressed GUID (e.g. 6F90CEC6801926076A29B2BCCAEEB38D). I found a Website where one can run a script to do this. Find the following code on the website and replace the right side with the GUID from the log.
string inStrGUID = "{6CEC09F6-9108-7062-A692-2BCBACEE3BD8}";
Open the registry (as an administrater) and search (Edit -> Find...) for the compressed GUID (uasually it's somewhere in HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Installer\UserData\S-1-5-18\Components\)
Delete the folder that is equal to the compressed GUID. The values inside the folder should be a path to the dll.
Once deleted select the parent folder (...\S-1-5-18\components) and hit Edit -> Find...
Repeat these steps (4-7) for all components from the log file.
It's also a good idea to delete all files still present in the original folder that weren't uninstalled.
Can one prevent this from happening?
I don't know. This really isn't that easy to reproduce. Some other post on SO have suspected the install/uninstall option in Visual Studio to be the cause of the problem but I have a different theory:
This bug might be the result of RemoveExistingProducts in InstallExecuteSequence in the Setup being executed too late and therefore not removing dlls at the right time. This bug is known for years and can be fixed by doing this. If you need help with Orca this explains how to install it.