Once installed, a number of files are placed in the Windows Installer Program Files' Clean-up folder. If you're using a 64-bit system, the files are placed under Program Files.
To uninstall applications, run msicuu.exe as an administrator, which will launch the Windows Installer Clean Up window, as the following figure shows:
Select the program to uninstall and click Remove. Once the application is removed, you should be able to re-install it without encountering any errors that say the application is already installed.
You'll also notice a utility names msizap.exe in the Windows Installer Clean Up folder. It's the application that actually performs the .msi-file clean up, and you can run the utility directly from the command line to remove specific applications' .msi information.