I have a solution in Visual Studio that includes a Setup project (MSI). The Setup project needs to install/uninstall a product in the same solution. However, for versioning purposes (we permit having different versions of the same product installed on the same computer at the same time), we wanted to have a Start menu folder for the product named like this: [Manufacturer] [ProductName] [ProductVersion].
To resolve this, we needed to not use the standard "User’s Programs Menu" folder available to be added in the File System section of the Setup, and instead we created a custom folder, using this default location: [ProgramMenuFolder][Manufacturer] [ProductName] [ProductVersion]. We put the shortcuts to the product in this menu.
Installation worked just fine. However, uninstalling succeeded also, but the custom folder was not removed from the system. To resolve that one, we needed to set AlwaysCreate property of the custom folder to true. After this setting and rebuilding the setup project, it worked! Strange but at least resolve the issue! Maybe somebody else would have the same issue in the future and hopefully this will help.