For 8-bpp LUT graphics, Windows 3.x had a palette negotiation mechanism in the API that reserved 20 color entries to the OS and let the focused app control the remaining 236. Applications that weren't focused got a combination of whatever was left over and dithering to fill in the gaps. (In 4-bpp modes, the palette was entirely fixed.)

This wasn't necessarily a bad solution to limited hardware, but non-LUT modes with 16 bits of depth were a huge, huge improvement once they were available.