Unchecking "Save recently played items" in preferences could also hide "Recent" list in a Windows context meniu
(VLC v.2.2.1. for Windows, OS: Windows 10, same in Windows 8 and 8.1.)
To hide recent media history, I went to tools>preferences and unchecked the "Save recently played items" checkbox, then clicked "Save", closed VLC and then reopened it. The "Open recent media" menu item in Media menu was gone, but I still could see "Recent" list in the context menu of the opened VLC window (which is probably controlled by Windows).
It would be great, if user could also instruct Windows itself to not track history of files opened via VLC.