I have 20 year old notebooks that are mostly filled with pencil and I refer to them occasionally. They are all perfectly legible still and I used a wide variety of pencils.
For true lab notebooks pencil is unacceptable because of their erasability, not longetivity. A formal lab notebook is used in such a way to provide a nearly immutable record. That's why corrections are done with a single line, blank space is blocked out, the notebook is bound with numbered pages and used chronologically, etc.
In a college chemistry class I took our lab notebooks had carbon(less) copy paper for every page. It made handing work in easier, but it also made an unerasable copy of the original record. Quite handy.