Berzerk2k2: I closed GOG Galaxy and started the game again using the Desktop shortcut and tada the game launched just fine.
I really want to know now why GOG Galaxy prevents some games from launching while others just work 100% fine no matter which way you start them.
I can't give you an educated answer as I have never installed Galaxy and never will if there's an alternative, but it sounds to me that Galaxy is using some kind of file lock on those files which prevents using them.
Is it possible that Galaxy somehow thinks the download is not yet completed, and keeps the file locked as an active download?
Something like that has happened to me with other software.
Sometimes it has even happened with game downloads that the download is actually complete, but the browser doesn't realise that, and doesn't rename the complete file automatically. It's obviously a completely different problem than yours, but my guess would be that Galaxy thinks the download is still active and needs to be completed.