I've been reading up on images with indexed color, and while most indexed image formats are limited to 256 colors, there are apparently image formats that support larger palettes.
According to Wikipedia
Indexed color images with palette sizes beyond 256 entries are rare
I did some extra searching, but I can't seem to find any clear list or mention of specific image formats that support larger color palettes.