Please accept my genuine apologies here, I think I must have crossed some wires / be operating under different assumptions / be talking past you somehow.
To clearly state my position, I believe:
a) Publishing a list of sha256(.au phone number) is equivalent to publishing the list in clear
b) We are discussing the set of phone numbers of affected Medibank customers, which could be described in a variety of ways (e.g. bitmap, dumb list, hashed list, bloom / cuckoo / xor filter etc).
c) There is basically nothing efficiency wise you need to think about to provide lookups in a database of phone numbers if you don't care about security. It is "laughably small data". All Australian phone numbers will fit comfortably in an Excel spreadsheet, Sqlite database, greppable text file etc.
Finally: Phone numbers and emails are a little weird. They are PII but the seriousness of their disclosure depends on context. Imagine a publicly posted list of porn purchases or medical conditions by phone number. It has a sort of "casual privacy" about it but is quite transparent to each user's contacts.