Why would leaving it off for 5 minutes make any difference? If its off then its off. So restart it a second later if you want, its the same thing.
When restarting a PC or laptop, you should always let the Hard Drive 'spin down' (ie, let it stop spinning like a CD and this can take a few seconds, not a few mins). Also, if you are having problems, try removing the battery and power cord and hold down the power button. This discharges the capacitor and will give you as clean a startup as you can get without delving into the bios/software etc.
It may be a bit of a joke, but uninstalling the offending software, rebooting and reinstalling (and possibly rebooting again) can solve many a problem with computers.
Also, you should use Control Panel - Add/Remove Programs to uninstall the software.
This can in some cases (Compuware, I'm looking at you) result in entries remaining in the Registry.
CCleaner can be used to remove unused Registry entries (which may result in the next install of the same software to have the same problems as the previously-removed version) and also remove unwanted files (temporary files, internet cookies etc) as completely and securely as possible.
WARNING: Messing about in the Registry should not be taken lightly, as you may screw up your machine, and should not be undertaken if you are not completely comfortable with it.
Having said that, if the files are in a directory like /HKEY_USERS/VLC/... or /HKEY_CURRENT_USER/VLC/... or /HKEY_LOCAL_MACHINE/VLC then you can probably get rid as they should relate to VLC only.