Insofar as not removing all the files, check the reference count under
[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\SharedDLLs]
If you've used MSIZAP
aka the "Windows Installer Cleanup Utility" you've basically put your machine into an unknown state and you'll need to manually remove everything from the registry (in my company we have a utility that removes all known registry entries from the last 10 releases of the product, basically consisting of a 1000 line .reg file and some other tools) before you can reliably test your setup again.
See http://robmensching.com/blog/posts/2009/3/6/More-on-Haacks-Troubleshooting-Windows-MSI-Installers for a bit more information about what happens when you get your machine into an "unsupported state" and how you'll need to manually clean up things or reformat before continuing.
We came across this problem as Installshield automatically defaults to setting components as shared components, so we'd end up with weird reference counting bugs, files left behind, etc, etc. A really ugly solution.
For your upgrades, try doing major upgrades rather than minor upgrades (patches) as this is a lot easier to get your head around when you're first getting into Windows Installer. But first, you'll need to get your app uninstalling correctly, then you can move onto the upgrade. If it won't uninstall properly, it won't upgrade properly.