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.
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.