As for Universe, I'd like to know for sure how they achieved the amount of colours they used in that game. It's possible to change the entire palette several times on the screen, so perhaps they did this? Cut each background image into wide chunks, remapped them to 32 colours (allowing some of the colours for Boris and the other objects) and did this several times for each image, then combined them (creating an odd looking picture at first) then the palette changing trick is applied and the whole screen is using more colours then. This might not be THE way they did it in Universe, but it's totally possible in OCS so anyone CAN do it if they want more colours in their games.
They probably made a tool which downgraded 256 colors pictures to 16 colors / line ones and generated the adequate optimized copperlists (i assume that this tool was also keeping an history of the palette modifications / line while redistributing the palette so changing all 16 colors wasn't necessary for every line).
It probably also dithered the pictures to cut the number of colors by half prior to this.
Extra object were drawn on 5 planes thus allowing exclusive use of the 16 higher colors of the palette for them.