Owen before I purchased an iPhone I went to one of the local Apple stores, who advised that they could only sell me one with a contract, Vodphone in their case.
I dislike Telstra with a passion, but they have far superior national coverage, so I stick with them, as much as it galls me to do so.