Laser etched quartz or diamond. There was an article about it in the last few years but I cant find it. I'm pretty sure 10,000 years was the time mentioned.
I don't know, but at that point we've left this problem domain and entered a new one: archiving digital data. That sounds like a daunting problem, but one that lots of people and institutions are strongly motivated to solve. If they were to come up with something, it would presumably work as well for digitally-encoded scents as it would for anything else.