I had the same MSI problem that was not removed when the package was removed, and the reason was pretty simple.
MSI was created in the same Visual Studio solution and was installed as a package project dependency. Each time a package was created, an MSI was first created.
The main reason for the removal was not the MSI product key set to "*", and therefore it must change every time it was created. This somehow prevented the removal. When installed on a fixed GUID, uninstallation was successful.
source share