Dug deeper, and found out the following:
Renaming the .exe of the programs in question allows them to be executed, but they cannot find a single threat in the system, while the problem still exists.
Hi,
So as it happens I somehow managed to contact an exceptionally annoying malware that seems to block the running of any anti-malware executables, regedit, or any conventional means of removal, even in safe mode, with most services turned off in msconfig. On startup it also opens the website "gangnamgaming.net", but doesn't seem to affect the computer in any other ways than these.
In general, I use Malwarebytes to scan for threats, but - as mentioned above - the current threat doesn't even allow starting up such a software (neither CCleaner). Also, I'm using Avast Antivirus, which - as usual - didn't find any threats, not even with multiple deep scans.
Do you have any tips on how to remove such a malware, or at least how to find out what exactly it is?
Thanks in advance,
Ben

Chowhound
Comic Vine
GameFAQs
GameSpot
Giant Bomb
TechRepublic