If it doesn't show in revo, then it's not stuck in the add/remove programs list. I'd just go to msconfig if it is an autostarting app and disable it, then delete the files in program files. If you want it 'nice' you can then go in regedit and go to HKEY_CURRENT_USER, software and look for Vidalia (or company name) and delete it. If it's not there, then go to HKEY_LOCAL_MACHINE instead, then do the same as above.
After all this, you can also run a reg cleaner, although many people will advise against it. It really isn't necessary.