When ALL ELSE FAILS.....
I put this in caps because this requires editing the registry.... But first some tricks to removing.
If you still have the program, try reinstalling it. Once you reinstall it (In the same location as the original) Then try removing it thru add/remove programs.
If you still can not remove it that way.
It is time to hack up the registry.
<--Insert standard editing the registry disclaimer here-->
Basically you remove all instances of the program.
THIS CAN HAVE BAD EFFECTS, UNFORSEEN, THOUGH
Before editing the registry, Back it up. Once it is backed up, then do a search for the application name. You may have to do a couple of different searches using different key words.
Important.... Before you delete a key, Read the key very carefully, make sure that any path's listed are for the app that you want to remove. And then Export that key before deleting it. You can never be too careful.
Also look for any paths that go to directories other than the program files (ie. winnnt\system32)
Once you get rid of the registry keys. You can then delete the program files. If there are files that you can not delete because of access denied, reboot the machine. The registry should not load those files. If it does, do a search in the registry for that file name.
FYI- regedit allows you to search.
(start/run/type regedit press run)
Good luck