Tyvek, perhaps? I'm not sure how long-term it would stick around, but it wouldn't decay as fast as paper in an unprotected environment.
I'd be more worried about toner de-lamination than paper deterioration in that case.
It's vulnerable to moisture, mold and insects, though.
If you can solve problems with breakage, very little is going to compete with glass or ceramic. So, something it's hard to apply breaking force to: Maybe etch glass balls, add some impurities for visibility, then re-coat with more glass for protection. A handful of beads will survive nearly anything.