BC1 uses 4 bits per pixel without being limited to 16 colors though.

In a way the hardware-compressed formats are paletted, they just use a different color palette for each 4x4 pixel block.

Having said that, for retro-style pixel art games traditional paletted textures might make sense, but when doing the color palette lookup in the pixel shader anyway you could also invent your own more flexible paletted encoding (like assigning a local color palette to each texture atlas tile).