add/remove programs is ok to use. In the admin or installation guide (for 4.5 at least) I think it listed the files that are not removed. these can be deleted manually. I can't rememer if it listed any registry keys that are left though.
You are correct, the add or remove programs does not remove everything and some left over files may affect the next sd installation. Have a look at the numerous sd 5.0 release notes. In one of them, there is a recommendation on uninstalling or pre installation. Basically, from memory, you need to manually delete the HP openview folder. Same deal for the registry but provided you do not have Openview Operations or NNM on the same box as they shared the same folder and registry. The other critical bit, is the administrator local settings for the temp folder where a lot of the sd installation temp files and msi resides and config. So clean that out. I think there are 2 or 3 environment variables used for the installation that can be removed if you plan to use a different sd installation folder.
What i do is, use Un-install, then remove the folders and cache. The do a registry clean up. Normally, i take the back of registry before installing. After uninstalling and deleting the folders, cache, and temp file, restore the registry.