I was at a customer the other day trying to uninstall a broken Veritas BackupExec installation. I then stumbeled over a utility called Windows Installer CleanUp Utility. it can help you get rid of those stuborn installations from Add/Remove programs.
Links: