I've noticed quite a few solutions listed including unofficial patches, workarounds, and switches on the boards. I tried most of them and had no luck. Then I tried messing with compatibility mode myself and got the game working completely with the movies as well. I hope these settings help someone else to get this classic working. People could reply to this thread with settings that work for them, if they're different from mine.
These settings worked for me on Windows 8.1 Pro x64 using an AMD Radeon HD 6530D
Under the compatibility tab for the shortcut of the game or NOX.exe itself
**Check Run in compatibility mode for then select Windows 98 / Windows Me from the drop down menu
**Check reduced color mode and select 16-bit (65536) color from the drop down menu
**Check Disable display scaling on high DPI settings
leave everything else unchecked

Settings that worked for me:

Downloaded the GOG installer;
Installed the game;
Runs fine every single time.


[EDIT] I was just joking and didn't mean to troll or make fun of the people that can't run the games they buy, what the OP is trying to do is great, sharing what knowledge they have in order for more people to play the game with none to minimal issues. With that in mind, let the downrepping begin.