Update:

Signed up to Telstra permanently. N900 works fine everywhere I have been so far using telstras extensive GSM and 3G networks.

Sold the free HTC Desire they gave me on ebay straight away

Will be buying xperia x10 mini pro when I move out to the bush.