Clearly mailmen would just be expected to use their phones to decode the addresses on demand, because everything is supposed to require a phone and an internet connection these days.
A bit more realistically, the address could be printed on a sticker by the sorting machine, the way address redirections are handled.
> A bit more realistically, the address could be printed on a sticker by the sorting machine, the way address redirections are handled.
Fun fact: PostNL already does this with 100% of the mail processed. The first step in the sorting process is to OCR the address, generate a "KIX" barcode[0], and print that on the letter using special ink if not already present. It's not intended to be user-readable, but anyone with a smartphone can trivially decode the unique destination address from it.
For a mail/parcel carrier relabeling anything is (somewhat surprisingly) a significant added cost (and there is not that much of margin), so they will do everything in their power to not do that unless absolutely necessary.
PostNL relabels approximately all parcels addressed to me (I almost always have to change either the delivery date or location to one convenient to me), completely free of charge.
Free of charge to you and free of charge to the sender. Which is exactly my point, for PostNL it is a sunk cost and if that will happen for significant amount of their consignments it would be an issue.
A bit more realistically, the address could be printed on a sticker by the sorting machine, the way address redirections are handled.