Nothing like paint is ever going to be really permanent. I've seen
people use cut out pieces of CD's under their more transparent
stones. That should last. However, if the idea of putting plastic
under your gemstones offends your aesthetics, here's what I've seen
done on historical pieces, perticularly under old rose cut diamonds.
They used pure tin, either in the form of foil trapped under the
stone, or actually "tinning" the inside of the bezel, by applying a
soft soldering flux and heating the article until the tin melts (275
F? or so?) then using a small steel brush, spreading it around to
help it adhere to the metal. It can even be burnished to a nice
shine. If it's reagent pure tin (from a chemical supply company),
it will take a very, very long time to tarnish.
David L. Huffman