techsoldaten is on the right track. Stone is hard to beat for longevity and resistance to damage. Hieroglyphics are sufficiently decipherable to allow scientists to decode them from scratch. Any serious millenial-class storage would need to take these features into consideration. Remember: If all you care about is longevity - to quote Dr. Strangelove out of context - "there's no limit to the size!" Nobody said it would be cheap; but take a look at what it costs to house, maintain and restore ancient artworks. techsoldaten has it right.

If you want your art to be recoverable (in some form) 5,000 years from now, you need to make assumptions about not only the temporal journey and potential hazards therein; but also the nature and technical sophistication of the society that is likely to attempt to recover it. The fewer incorrect assumptions, the more likely it will be recovered.

I find this topic fascinating, on many levels. It's all the more fascinating because even serious archivists can't seem to get beyond the next 100 years or so before their preservation schemes break down.

I wrote a paper about this problem in 2003. I was examining practical innovations that - while expensive - could virtually guarantee recoverability 1000+ years into the future.

Here are my criteria:

Must not depend on industrial infrastructure (Mad Max scenario)
Media must withstand fire, burial or submersion in seawater
Media must contain detailed instructions for reading it in multiple languages
Encoding scheme (and metadata) must be straightforward and obvious
Encoding must be sufficiently redundant to withstand significant damage

Tough, eh? There are solutions. One solution is to also build a reader/decoder that can withstand burial, submersion, fire, physical damage, etc.

On a shorter time horizon, if you allow for an industrial infrastructure, microfilm has an estimated lifespan of 500 years. It can't withstand fire; but it should withstand burial and submersion.