I've received a second response from GOG support with one more suggestion that has not been mentioned in this thread. I have not had a chance to try it yet, but posting it in case it helps any of you.
"Please try to force V-Sync for this game. In order to do this you need to open your Catalyst Control Center (right-click on empty desktop space and select it). In Catalyst Control Center, go to Graphics -> 3D -> All, once in there scroll down the list and select - 'Wait for vertical refresh' and and set it "Quality - Always on" option on far right on the slider.
Once that is done hit the "save profile" button. It will ask you which .exe file you want to apply it to. Go find the game installation folder (default: C:\GOG Games\game-title\) find game executable file, and choose it. Apply settings.
If my instructions here aren't exactly right, you should still be able to figure it out from that screen in the Catalyst Control Center. It can't be little different, because AMD changed layout for some menu options."
I guess it might be worth a try for any of you with NVIDIA cards to change v-sync in the equivalent NVIDIA settings too.
Oh boy, forcing VSync? Who do they think we are? That's one of the first thing we all probably may have tried already. I thought they were professionals but this is 101 of simple support. Anyway at least for me I FOUND a possible fix (it works for me). It is a workaround but no mouse flicker and all videos are still working. Cannot guarantee the game may not crash at a time but it seems to work. Here is how I fixed it for me:
Since the problem obviously have to do something with how the screen is drawn I suspected directdraw to be the thing I'd have to deal with. I managed to get some old DDraw games to work using a free and open source DirectX Wrapper. The problem with it is that it has many many checkboxes and options and it's hard to find out which one you'll have to check. I experimented about half an hour and found a setting which worked for me.
-First download the wrapper here: http://sourceforge.net/projects/dxwnd/files/latest/download
-Extract it anywhere and start dxwnd.exe
-Click edit and chose add in the menu
-In "Name" you can enter whatever you want ("Starship Titanic" would be a good name I'd guess ;))
-In path chose the executable of the game (st.exe) NOT only the path itself
-In the register "Main" uncheck "Hook all DLLs" and check "No banner" (splashscreen), "Keep aspect ratio" and chose "Desktop" instead of X,Y coordinates
-In the register "Video" check "Lock sys colors", "Lock reserved palette enties", "Forces 16BPP desktop" - also chose SVGA modes in screen resolution and limit it to 640x480
-In the register "Compat" check and chose "Windows 95"
-Double click on the green lit entry Starship Titanic (or whatever name you chose)
Hopefully I haven't forgotten any checkbox you have to change. I will test it again to make sure and will edit my post if I have forgotten something. Hopefully this helps others. It helped me getting mousepointer back on nvidia GTX960 Win7/64 Dx11.
Edit: Checked it again with a new profile - if you only change what I have listed above it should work.