This issue appears to be caused by Explorer.exe resetting the system palette, essentially overwriting the palette defined by the game (hence the rainbow colors). This is evidenced by how taking a screenshot of an affected game will show just the discoloration with black where the other game assets would be rendered and by the fix itself.
A more technical explanation: These games rely on DirectDraw, an API in DirectX which was used to render graphics which is now deprecated. More specifically, they used an exclusive palette, where they set the system palette (the colors the system can use, back when there were only 256 colors) to the palette the game wants to use. However, some applications try to set their own exclusive palette, causing conflicting colors since the game's exclusive palette is no longer actually exclusive and is set to the wrong colors. In newer versions of Windows, CSRSS and the desktop window (explorer.exe) set their own palette, which causes the odd colors.
PalettestealerSuspender prevents palette issues using a different method.
The fix can be scripted with a BAT file which will kill Explorer.exe, run the game in question, and then restart Explorer.exe once you have exited the game.
taskkill /F /IM Explorer.exe
[Path to game executable]
You can place the BAT file on the desktop for some games, but others require that it be in the same folder as the EXE. In those cases, only use the executable name in place of the entire path and create a shortcut on your desktop to the executable.
DxWnd was originally created to enable old DirectX games to run in a window. Nowadays it provides far more features: It can fix the odd rainbow color issue, enable time stretching, and you can decide between running the game in a window or in full screen.