Most efficient way to check if key exist on a table
Using Bloom filters you can store membership of $n$ elements using approximately $-1.44\cdot\log_2(p)\cdot n$ bits, where $p$ is your probability of a false positive (it does not have false negatives).

This is assuming you have perfect independent hash functions (which is a reasonable enough assumption).

So if Albert wants an 0.1% chance of wasting his time the postman needs to carry $\approx 14.4$ bits of information per address, which is definitely less than the amount of bits to uniquely store an address.