Comment Prior Art (Score 1) 141
There's even some of the original documentation around for parts of it (though not expressly for unclaimed mail) from 98 / 99.
a-guide-to-printing-the-4state-barcode-v31-mar2012.pdf - although the document is dated 2012 - that's just the most recent revision - the original dates back to the June 1998 (as listed on Page 2).
This 1999 document australia-post-addressing-standards-1999.pdf references "Specification Number 203-4-State Barcodes" - which likely would also contains the same information.