|MadSci Network: Earth Sciences|
Hello, Stev! Many materials will last more than a million years, in the right environment. For example, one could use gold (which is chemically inactive) and as long as you don't have hydrothermal solutions around (i.e. bury whatever you want to save in a continental craton) you stand a reasonable chance of having whatever's inside the gold envelope last for a long as the geology of the planet doesn't go volcanic there or suffer faulting. Most native gold that is found in mines has been there for considerably longer than one milliion years. Similarly, you could use a number of refractory metal oxides (e.g. TiO2, HfO2, Ta2O5, etc) or silicon dioxide in any geologically "calm" environment. Quartz crystals mined in Brazil are some hundreds of millions of years old, so certainly at least SiO2 can last a very long time. The key is not the material so much as the environment you put it in.
Try the links in the MadSci Library for more information on Earth Sciences.