I think this has to do with when your RemoveExistingProducts action is scheduled. Installshield moves this action around in the sequence depending on the UI selections you make on the Upgrades view. Personally, I find both options to be flawed and I will explain why.
1. Completely uninstall old setup before installing new setup.
This option seems to be the one you are looking for (and likely the one you selected). The issue here is that Windows Installer is always trying to be efficient and not have to do any file changes if it doesn't have to. If you review where your RemoveExistingProducts action is in the sequence when this option is selected, it is after File costing. This is important for a couple reasons. 1. All components are checked to make sure they are required to install. This includes components with only shortcuts added to them. In the case of non-versioned files, there are special rules about how they are handled. These rules may result in the component not getting installed. 2. There is a communication problem between Windows Installer and the .Net framework. Basically MSi asks .Net if an assembly is present during Costing. The response is yes and the component is marked as "Do not install".
Both of those actions ignore the fact that the RemoveExistingProducts action will be removing the entire old version before it installs the new one. Thus everything should be marked as install.
2. Install setup then remove unneeded files.
This has all the above problems since the action is scheduled near the end of the install process.
Careful versioning rules must be followed by your development team to get this to work.
I never use it since I don't care about efficiency like Microsoft does.
That was the bad. Now the good.
If you select "Completely uninstall old setup before installing new setup" then manually move the RemoveExistingProducts action to after ValidateProductID in the execute sequence, you should get the behavior you are expecting.
Why do I do this?
Really the only reason is that it comes before File Costing. All the same questions and comparisons are made by Windows Installer during Costing but with nothing to compare to, everything gets marked as "To be Installed".
The result is, a major upgrade UI sequence runs, it removes the old product, then installs the new version. I have been using this setting on my products without issue. Give it a try and see if it helps your situation.