A couple of debugging suggestions off the top of my head:
Try creating a new Basic MSI project and compare the details in the dialogs manually in Installshield. Add some test files for your new project and make sure it uninstalls in all ways (especially the way that is not working for your main setup).
If nothing obvious is seen or you want a more effective comparison use Wix's dark.exe file to decompile your compiled MSI to Wix XML format for both your origiproject and a fresh one. Then locate the Wix XML for the dialogs and check the settings.
Version control your install source! When problems like this surface you have much better debugging opportunity - including just reverting the whole setup a couple of revisions and re-doing just what is missing in the old source.
If you can get the new setup working and the old one isn't cooperating, it is not that complicated to migrate all components from the old setup to the new one. I did this to migrate from Installscript MSI to basic MSI using an "Export into project" option available by right clicking each component (I believe that's where the option was). It took me just a couple of hours for a large setup. Then it tool a few further hours to verify all custom actions properly.
For the record: using Wix with text based source files makes debugging a whole lot easier and is highly recommended: Windows Installer and the creation of WiX. Once you get used to it you can match the speed of creating an installer with commerical tools.
Details on Wix, including quick start suggestions:
MSI vs nuget packages: which are is better for continuous delivery?
For more help on installers check out: http://www.installsite.org/