In a number of applications we create an MSI Installer with the Visual Studio Setup Project. In most cases, the install works fine, but every now and then the previous version was not uninstalled correctly. The user ends up with two icons on the desktop, and in the Add/Remove program list, the application appears twice. We have yet to find any pattern and in most cases the installer works without any problems.
Do you have an example of, say, two installs where this happens that we can try to examine? If you can post a link to them, we might be able to learn more about what's going on. As it is, any number of things could be happening... we basically need to see an example of what's going on.
What happens when the uninstall of the previous version fails depends on the sequencing of the RemoveExistingProducts action. I have written a summary about the various options in the past: http://jpassing.wordpress.com/2007/06/16/where-to-place-removeexistingproducts-in-a-major-msi-upgrade/.
Unfortunately, you do not have control over RemoveExistingProducts sequencing when using VS setup projects (Unless you edit the MSI with Orca after it has been built, which usually is not practical). But if your setup project is not completely trivial, I would strongly suggest you to use a different MSI authoring tool like WiX or one of the commercial tools anyway.
I have the install log file from one of the installs where this occurred. I have looked through it, but was unable to see any indications of a problem. Would it be worth posting it?