as an addition to all mentioned workarounds: I used the Registry tweak and all help I could find on a machine (64-bit Pro) where .exe-files were connected to VLC player. It still wouldnt work after reboot.

Uninstalling VLC Player seemed to solve the issue then (with a rebuild of the icon cache). But only until I reinstalled it, then everything went bad again.

So the solution was to uninstall VLC and then manually remove every Registry Key that pointed to VLC Player. Some Keys needed to be deleted with SYSTEM Account Rights.

So you can use this if you are stuck in the same way. BUT you should be familiar with getting SYSTEM account rights and removing Registry Keys. If you are not, just leave it to some IT guy you might know.