I've discussed a couple different reasons that Windows Installer 3.0-style patches - those with the MsiPatchMetadata table in the patch package itself - might not be uninstallable. I explained another reason in a discussion about the new patch build support in Windows Installer XML (WiX) v3 recently, describing why unchanged files should not be updated via the patch package. This happened with our own legacy patch build system for some internal releases of Visual Studio 2005 Service Pack 1, but was fixed before VS 2005 SP1 was released.

When files are patched, the file sequences are updated to locate them in a cabinet embedded in a patch package, and the Attributes column in the File Table is updated to add the msidbFileAttributesPatchAdded (4096) bit to each file in the patch. However, with the default file version rules in effect - which would be the case with the default REINSTALLMODE property value of "omus" - unchanged files in the patch do not overwrite those files on disk, and if the files on disk are not overwritten they are not copied to the baseline cache.

When the patch is uninstalled, Windows Installer determines from the File.Attributes column that the file was updated, and attempts to copy the file from the baseline cache back to the file's target path. Because the file wasn't overwritten when the patch was applied and, therefore, is not in the baseline cache, Windows Installer attempts to resolve source during patch uninstall. Unless the product installed and registered its own cache like the Microsoft .NET Framework 2.0 and newer, the user will be prompted with a dialog asking for the location of the original installation package; however, if this maintenance mode installation is silent or the original installation package is not provided patch uninstall will simply fail.