There's no such thing as a "better optimal palette". It doesn't exist. If you have an optimal palette, it is, by definition, as good as or better than any other palette.
You can't make it better!
The fact that I'm looking for an algorithm to generate an *actual* optimal palette is what's causing the problems. :P