How was it "removed" originally? Have you deleted the programs folder for it? Are there any executables still running?
If you are just seeing it in Add/Remove programs and no place else, that's a registry edit.
You must find the listing for the program under this key (run regedit):
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Uninstall
And right click on it and delete it. It's possible it might be one of the "clsid" keys (numbered entries). If you don't find a program folder name, you must open each clsid and look in the right pane for it. If you are in doubt, don't delete anything, or select File > Export and save the key first as a reg file. You can restore it by doubleclicking