First, back up the Registry. You can back up the Registry in Windows Explorer. Select View-Folder Options (or View-Options). Click the View tab, select Show all files, and click OK. Now create a folder called C:\Regback. Go to the Windows folder, find the files system.dat and user.dat, then hold down as you drag those two files to C:\Regback.
Now select Start-Run, type regedit, and press . Find HKEY_CLASSES_ROOT\*\shellex\ContextMenuHandlers in the Registry Editor's left pane. Click the plus sign (+) next to "ContextMenuHandlers" to see keys resembling Windows Explorer folders for every program that has options in the context menu. Then select the key for the program that you thought you uninstalled.
Double-click the (Default) value in the right pane to bring up an editing box that has the Value data field highlighted. Press -C to copy this string to the Clipboard. Then press . Right-click the open key in the left pane and select Delete, then Yes. Press -F to start a search. With the cursor in the "Find what" field, press -V to insert the numbers that you copied from the Value data field. Uncheck the Values and Data fields and click Find Next. The search should stop at a key inside HKEY_CLASSES_ROOT\CLSID. In the right pane, the default value's data should describe the program. Press and then select Yes. You should never see the dearly departed program's menu option again.