If you are super paranoid you may want to look into thermal transfer barcode printers (not to be confused with thermal printers*). They can use resin cartridges and tear resistant (tyvek) labels. Once printed a resin wax label is not going to be affected by water, age, sunlight, moisture, and normal heat (excluding a fire). The higher quality stuff (name brand Zebra ribbons) resists solvents, bleach, cleaner, gasoline, etc. They routinely are used in warehouses and other dirty, hazardous areas and last ... forever. Pretty routine for a 10 year old label to still scan with a barcode scanner.
Thermal transfer printers aren't cheap (usually $300 to $400 or more) but if someone was looking to paper wallet say 1000 BTC I wouldn't use anything less.
*Slighly confusing but thermal printers have no ribbon they use a printhead which produces heat to cause a chemical change in paper. Everyone has seen the faded receipts from a thermal printer. The same technology however can be used to apply with high precision a layer of wax or resin onto a paper, or plastic card. The later are called thermal transfer. Most thermal transfer printers can do both (direct thermal or thermal transfer).