The Coleman-style cylinders stay fresh forever (it seems) as long as humidity doesn't rust the connection surfaces.
My stash includes some that are at least ten (more like twenty years) old. I used some of them last month and they worked quite well. I stock both the Coleman cylinders and the smaller Lindal valve cylinders, pretty much standard for backpacking canister stoves.