Stone - and more usefully, clay - last almost forever, but they're impractical for digital storage, since there's no useful way of imprinting on them that isn't very low density, unlike paper.

Unless we could improvise something with old-school dot matrix impact heads to print on clay - I wonder if anyone has tried.