Utopia, which I ripped gfx from just the other day, used a mask of some sort (5bp+a mask). Here's a screen, using the RetroSpec Ripper:

(I made a duplicate palette (index 32-63) so I could see the stuff correctly in 6bp mode, but in the end I had to write my own ripper cuz I needed to rip using some header variables for image heights)
As for my 16 color palette project, I'm just treating it as an optimization problem. I will use it for my handtop which I will travel back in time to launch. It has my 16 color palette, 4bp per sprite + 1bp opacity mask, or something like that. Not necessarily a speccy but I made the mockup today so it'll have to suffice as an illustration.
