Un-installation of the package is not supported

I'm trying to generate an MSP out of the latest and previous MSIs as in the scenario below:

• The previous MSI is fixed and used as a baseline.
• The latest MSI is generated with the new modification on the files included everynight and it will get a new ProductVersion on every generation (which happens with every build on the server).
• The previous MSI that is the baseline is installed on the machine; let's say it has version 1.0.0.0.
• The MSP generated on the first build is installed successfully, now the product version is 1.0.0.1.
• The latest MSI now is 1.0.0.2 and has new modifications in it and we want to generate a new MSP to get those modifications to the machine, the MSP is generated based on the difference between previous MSI 1.0.0.0 and latest which is now 1.0.0.2.

The problem is that we are getting an error when trying to install the second MSP saying:

Un-installation of the package is not supported.

And below is the error log:

MSI (s) (78:EC) [07:57:01:214]: Final Patch Application Order:
MSI (s) (78:EC) [07:57:01:214]: {C39177DC-24FD-432E-9D50-159E7E3CC62C} - C:\temp\[Package Name].msp
MSI (s) (78:EC) [07:57:01:214]: Other Patches:
MSI (s) (78:EC) [07:57:01:214]: Unknown\Absent: {9BEBFF56-7735-4618-BF01-01E96548FA81} - 
MSI (s) (78:EC) [07:57:01:214]: Product: [Package Name] - Update '[Package Name]' could not be removed. Error code 1646. 
Additional information is available in the log file C:\Users\Administrator\Desktop\msp.log.

MSI (s) (78:EC) [07:57:01:214]: Windows Installer removed an update. Product Name: [Package Name]. Product Version: 1.3.0.0.81.159. Product Language: 1033. 
Manufacturer: [Company]. Update Name: [Package Name]. Removal success or error status: 0.

MSI (s) (78:EC) [07:57:01:214]: Product: [Package Name] - Update '{C39177DC-24FD-432E-9D50-159E7E3CC62C}' could not be installed. Error code 1646. 
Additional information is available in the log file C:\Users\Administrator\Desktop\msp.log.

MSI (s) (78:EC) [07:57:01:214]: Windows Installer installed an update. Product Name: [Package Name]. Product Version: 1.3.0.0.81.159. Product Language: 1033. 
Manufacturer: [Company]. Update Name: {C39177DC-24FD-432E-9D50-159E7E3CC62C}. Installation success or error status: 1646.

MSI (s) (78:EC) [07:57:01:214]: Product: [Package Name] -- Installation failed.

MSI (s) (78:EC) [07:57:01:214]: Windows Installer installed the product. Product Name: [Package Name]. Product Version: 1.3.0.0.81.159. Product Language: 1033. 
Manufacturer: [Company]. Installation success or error status: 1646.

Uninstallation of the update package is not supported.
C:\Windows\Installer\5d9684f.msi

Is this allowed to do? Or do we have to change the previous MSI on each MSP installation, so we keep each MSP with distinct files only?

Error 1646 implies that you're attempting to uninstall a patch that's not marked as uninstallable. There's not enough info to know if that is the case, sosome guesswork here.

In general your approach looks correct. The baseline is always 1.0.0 and the patch is always built as the delta betwen that base and each new MSI file. Your comment "..the MSP is generated based on the difference between previous MSI 1.0.0.0 and latest which is now 1.0.0.2." is a little misleading because the previous MSI was 1.0.0.1 in your examples. Perhaps you meant the base 1.0.0.0.

So you always build the patch as the delta between base and latest MSI, always create a new patch guid, and hopefully you're not changing the MSI ProductCode.

However, your ProductVersion examples don't match what's in the log. Product Version: 1.3.0.0.81.159 is not a valid version:

https://msdn.microsoft.com/en-us/library/aa370859(v=vs.85).aspx

so you can't rule out the possibility that the invalid versions are related to the error, especially if all the actual MSI versions are 1.3.0.0.