Thanks to my dad's suggestion, I contacted Telstra's disability department about mobile phones for CI users. They actually gave me a specific phone that will work well with the cochlear implant.
Of course, the phone is their own brand, LOL.
But we have found this great site which lists phones with high compatibility with hearing aids:
As that is American, now it's just a matter of finding out if those models are also sold in Australia.
Motorola Australia also has a webpage devoted to accessibility, including mentioning that all their phones are built with telecoil:
So there is information out there!