We'd like to use something like paper to print wallets for Justcoin, but need durability (> 10 years)
Use acid-free, archive-save paper conforrming to ISO standard ISO 9706 and an electrostatic printing process (for instance laser printing). Do NOT use a colour printer, use a B/W only printer. Do NOT use refurbished or value toner cartridges (you never know what crap they put in there). Keep in a darkened environment. For archiving purposes lasting up to several hundred years use archival quality paper conforrming to ISO standard 11108.
What are your thoughts on laminating as a way to preserve a printed paper?
It would highly depend on your specific purpose. For keeping your own records it is a certainly a valid method, especially the newer cold lamination methods. For papers of scientific historic value lamination is no longer recommended. A huge amount of historic papers was laminated with varying methods starting in the 1930s and it's been shown that the effects of certain lamination methods have a higher degrading effect on the paper than if the paper had simply been stored in a controlled environment (controlled for light, humidity, temperature).
Naturally you won't want to use hot lamination methods on simple direct thermal paper like the piper uses.