I made a mistake editing the msi package and saving it - thus creating a new GUID. This I think is the problem.
Active Directory is attempting to remove this package and I think the different Product Code GUIDS is causing confusion.
True. It's not the AD, it's the Windows Installer trying to locate the package for uninstall (typical if the package was installed in advertised mode). Further, the new codes are only created when you build packages, not when you save them.
Even though you may NOT know the product code, there exists a cached version of the package at %windir%\Installer. Locate the *.msi of the product and find the package code. How? When you click on each package, the status bar shows some information. Verify if the info is of your old package. If not, go to Properties>>Summary of each *.msi that exists at this location and find your package.
You can open this package in your Editor or ORCA and find the product code. Run the uninstall mode from the command-line for this product: msiexec /x {Product Code}
[You can also find the Product Code from the registry: Add/Remove section of HKLM]
The package may again look for source location and source file, furnish the above info at your UNC location. The uninstall should be successful.
Also, if you installed this package from SMS, the primary/secondary site (where you store your package for distribution) should have the old package unless you already updated the package at that location!
Is this something you were asking about?
NOTE: Always make a back-up of original items before you apply changes so that you can revert it later. Avoid having test installs in a PROD environment.