Upgrade of MSI
MSI (s) (94:CC) [17:29:07:520]: Doing action: FindRelatedProducts
Action ended 17:29:07: AppSearch. Return value 0.
MSI (s) (94:CC) [17:29:07:520]: Skipping FindRelatedProducts action: not run in maintenance mode
Community Chosen Answer
No two MSI's should have the same package code. You need to change the package code first for performing an upgrade.
If the msi is going to perform some minor changes then you can perform a minor upgrade by changing the package code and version alone.
For types of upgrades have a look here - http://helpnet.flexerasoftware.com/installshield22helplib/helplibrary/MajorMinorSmall.htm
The FindRelatedProducts action only runs the first time the product is installed. It does not run during maintenance mode or uninstallation.
Maintenance mode means that the product is already installed which in your case is true, as defined by the ProductCode guid and the PackageCode guid.
The ALLUSERS value must be the same for two MSI's. A per-user install will not upgrade a per-machine install, and so vice versa.