Hmm...I'm guessing it's filetype-specific then. In that case, you'll need to look under the keys for each extension that VLC is associated with under the HKCR tree, which is going to be a pain. Stick with the uninstall/reinstall method instead.
Oh, old thread here but also the first one that comes up when searching for "vlc context menus". The registry key is HKEY_CLASSES_ROOT\Directory\Shell. There should be two keys under this for Add to VLC playlist and Send to VLC playlist. Delete them and that's it. It's three years since this post and it still isn't an option in the application to do this. Ug.
I'm submitting a post for a feature request to add this ability to preferences. Maybe it'll get added some day.
The two main keys are:
Those only effect the context menus when you right click on folders. If you want to remove the context menus for mp3's and such, then the easiest method is to uninstall/reinstall and uncheck the file associations options.
PS. This may be an old post, but it is still the number one search in Google when looking up "remove flc from context menu"