Read through the thread. i know more about this issue then anyone randomly chiming in and adding their "Fixes".
Windows automatically forces 256 colours, and disables DWM prior to starting the game.
End tasking explorer doesn't solve the freeze, neither does affinity tweaks.
setting windows classic disables Acceleration for 2D (GDI and Ddraw) which one can do via the Dx Tools anyway (neither work).
The colour issue has nothing to do with the themes, Explorer causes a palette issue regardless of acceleration being available or not, regardless of themes, regardless of apps running.
Pausing Explorers threads prevents explorer from updating and intruding on the 8bit palette.
I have also discussed this issue with my programming professor and he agrees with me and has over 12 years of Microsoft programming experience.
Tell your professor to act or stfu. Microsoft programmers got shit all experience compared to the guys who write emulators in their spare time, Who btw have run the game through debuggers, decompilers and the like and still can't isolate the palette intrusion in the game and patch it out without killing activity in the shell.
Edit:
Combination Testing.
It seems the recent Compatibility updates did help, however you need the following.
Classic Theme with 256/640x480 compatibilty
Windows Aero Basic\Standard with 256/640x480 compatibilty
Windows Aero Glass 256/640x480 and Disable Desktop Composition.
And the consistency test FAILS.
I was able to run SC just fine with Aero glass on, but a reboot later and nothing i do fixes it.
So yeah, stuff your fix. Inconsistency relying on unknown circumstances trumps all.