I don't think there's a simple answer. For example, someone recommended black ink on white paper, but it really depends on the composition of that ink. Inorganic pigments last forever, but the ink used in black sharpies actually fades pretty quickly.

Pencil definitely lasts if the paper is undisturbed. I have some paperwork that's 100+ years old and with legible pencil text. On the flip side, if the paper is handled a lot, the writing will gradually fade because graphite particles just sit on the surface and can flake off.

On some level, the medium is your main problem. Low-grade paper, especially if stored in suboptimal conditions (hot attic, moist crawlspace, etc), may start falling apart in 20 years or less. Thick, acid-free stock stored under controlled conditions can survive hundreds of years.