Comment by ajb
One thing I've been meaning to try, but never got round to, is to stick a URL on an envelope, pointing at a page with an address, and see if the mail (royal mail, in my case) actually deliver it. I suspect they would but that it would take a few extra days. It's no worse than some of the addresses that they do deliver.
What about encoding the address as a QR code?
This should not require any Internet access to view by whoever is scanning it to be sorted for delivery.