Just for further info for Trans State... They advertise hiring Aussies, but when I spoke to them they hadn't actually hired any yet and seemed uncertain as to how the whole visa process works. It may be worth considering that if you run with them you may be the first one working out the wrinkles in their process.
Socks