OK that whole game freezing issue got me thinking. As already stated in other threads, it's mainly an issue with the cinepak codec not working properly.
This drove me to trying something so simple, it's almost ridiculous.
First, you'll have to delete the ICCVID.dll in the game directory. It's GoG's addition and was supposed to make these videos play on computers that don't have the cinepak codec installed (which by now is probably the majority). Unfortunately on many computers like mine it wouldn't work anyway, so for this solution, get rid of it.
Now the game won't freeze anymore, but all videos will be black.
I could open the .avi files in the assets subdirectory with VLC, so i figured: Why not convert them to a format i have proper codecs of? So using VirtualDub i converted the a236.avi (one of the first videos being played) to MPEG4 V3, and it worked!
If GoG still has any interest in getting this game to work for players out there, i would upload my recompressed files, MPEG 4 compression even reduces the file size significantly.