If it's not throwing up any errors or revealing its itself in any other way, it doesn't hurt just to leave the entries. If it's a program you really hate (BonziBuddy, Gator, etc.) do some manual cleanup.
Personally, I just run a search of the registry and delete any key that mentions the offending program. I know everyone warns about editing the registry and backing it up, but I've never had any problems deleting entries for uninstalled programs. Occasionlly a particular program (Yahoo comes to mind) will leave entries in a particular profile and a user will get an error message such as "C:\Program could not be found." In that case, you need to open their Ntuser.dat file (Load hive) in regedt32, go to Software\Microsoft\Windows\CurrentVersion\Run, and delete the entry.
Gator is a different matter altogether. It leaves entries everywhere: the registry, the Startup folder, Common Files. Two Gator processes (Gmt.exe & Cmesys) continue to run even after it's uninstalled.