It will be a lot easier to uninstall and reinstall without the link.
For each and every video extension, delete the keys:
HKEY_CLASSES_ROOT\(extension)\shell\PlayWithVLC
HKEY_CLASSES_ROOT\(extension)\shell\AddToPlaylistVLC
Make sure you don't miss any extensions.