In my experience S3TC pretty much always gives better quality than paletted textures. On standard color maps that is, though not on normal maps as you said where s3tc is useless. Most color maps compressed to s3tc will still subjectively look very good (though you can find the errors if you measure or look for them), while many if not most of the palette compressed textures have visible defects, IMO anyway.
I wasn’t talking about emulating the actual palette lookups as such. I was talking about the typical palette rolling effects, like the flashing object or whatever someone mentioned earlier in this thread. Effects where using a palette could be useful. These effects can all be achieved by other means, and are generally fairly simple to implement. I can’t even remember the last time I thought a palette would be helpful.
Also, given that paletted textures never were widely supported I don’t think the loss will hurt, people would have had to code a separate path anyway.

