Saw this elsewhere, some amazing work with palette cycling from the early 1990's.
http://www.effectgames.com/demos/canvascycle/

I remember seeing this back around the time it was made and being amazed by it. It's amazing what you can do with limited colors.

Someone also pointed out how Bungie used palette cycling for muzzle flashes in Halo 3. Pretty cool effect.

Some links on the wiki
http://wiki.polycount.com/CategorySpecialEffects

Weren't artists using palletized images to hide messages in game artwork. using 2 different indexs with the same RGB values you could add stuff to areas of an image. When 1 of the RGB values changed the messages became visible.

I can neither confirm nor deny. ;)

Right im off to mess with the palletes in blader runner!!

That is genius... I've seen it done all over the place but figured it was animation not pallet switching.

Some of those are just plain jaw dropping.