I was about to suggest rock carving 
But really, some kind of robust optical media should be the best for long term storage. I'm sure something better than CD is used by serious digital archivists
Probably something like Magneto Optical. In terms of media robustness outside of a piece of amber or a rock you're not going to get much better.
Problem is, the media and the drives are hideously expensive and the capacities are a fraction of DAT.
If you're that determined, you're probably as well off to use multiple sources for all important data. Gmail accounts make for great storage.
Then there are more specialised companies like box.net.
