We also encountered this problem where lower-versioned DLLs were not getting reinstalled on a major upgrade. I thought it was strange that the installer would decide which files to install based on the versioning of existing files, then completely uninstall everything, but still only install what what files had been determined to install before uninstalling the old product. This seems like it might be a bug in Windows Installer…
To fix this problem we moved the RemoveExistingProducts action above the CostFinalize action.
I know the documentation on MSDN recommends placing the RemoveExistingProducts afterInstallValidate, and I’m not sure if putting it before the InstallValidate action has any negative side effects for minor upgrades, but we have decided to only perform major upgrades for our products so this solution appears to work for us.