Quick Brainstorm: 1) You could have downgraded files? 2) you have mismatched component GUIDs? 3) you have removed files without realizing? (could work if older setup version had file set permanent) 4) you have missing pre-requisites? 5) custom actions can have deleted files? 6) virus scanners can have quarantined files?
There are edge and fringe cases. Right now I can only think of transitive conditions for components (msidbComponentAttributesTransitive => component conditions are re-evaluated on reinstall potentially removing the file), but that should not affect major upgrades I think.
Downgraded Binary: It could be an issue of a downgraded binary. Downgrading a binary in your upgrade setup (including a lower version file to replace a higher version from the original setup) can result in files being missing after the installation. Try to run repair from Add / Remove Programs and launch the application again. If this solves the problem and the application launches you very likely have this problem on your hands. An ugly fix that I have recommended for this is to update the version number of an old binary to a higher version using File => Open as resource in Visual Studio. There are other ways, but I use that approach for pragmatic reasons.
Logging: There are several other possibilities. The first thing you should do is to make a proper log file:
msiexec.exe /i C:\Path\Your.msi /L*v C:\Your.log
and then look for entries like these:
MSI (s) (0C:5C) [16:13:25:890]: Disallowing installation of component: {015A4DC1-56F4-562B-96B5-B3BE0D45FA5F} since the same component with higher versioned keyfile exists
MSI (s) (0C:5C) [16:13:25:890]: Disallowing installation of component: {4B6A1404-3892-5BEF-AB47-8FE3149211A4} since the same component with higher versioned keyfile exists
See this old answer from Rob Mensching himself. And here is more from Chris Painter.
Logging How-To: Here is an answer on MSI logging. I would just enable the global logging policy so all MSI operations create a log file in the TEMP folder.
Mismatched Component GUIDs: You should keep component GUIDs stable between setups unless you move files to another location (in the source media - in other words install to a different absolute target path). If you sequence the RemoveExistingProducts action to run late your component referencing errors might cause files to be missing after major upgrade as the setup enforces component rules in this scenario (with early sequencing these rules can be bent).
If you use mismatched component GUIDs - in other words you don't keep the component GUIDs stable for files targeting the same absolute path AND you use late sequencing for the .
When should you change component GUIDs? (recommended).
