I am in a similar position and would appreciate any advice - my Installer needs to function under Win9x/NT/2000, and generates logfiles and (many) other extras that have unique names (so RemoveFiles is not an option).
The product is being installed from a WinZip Self-Extractor, and I've had to disable the Change... option in Add/Remove programs: this is because users tend to click it and get an error message stating that the source MSI wasn't found (the temp install dir was deleted).
So, I have a custom action that recursively deletes the directories left behind by the installer, and a dialog box set up for the uninstall that asks the user if he wants this action to run. Obviously, the usual option (as worked for Leigh - using Change, then Remove) is of no use to me here...
So, does anyone have any other ideas on this? Any more input would be greatly appreciated!