It certainly was possible on the Amiga, although I'm not sure if dpaint could do it at the time of making Monkey Island 1. At least later versions supported HAM modes and of course when AGA arrived it did 256 colors too.