FYI: Verizon is a cdma cellular provider,surely phones that work with verizon have to be CDMA phone.
So,in short answer it WONT work with Telstra,just because Telstra is a GSM network provider.The rule is cdma phone work with cdma provider & gsm phone work with gsm provider.