With both of the "large" operators having head offices in Perth, I would head West before East. Although you seem to want to be in VIC, it may not be the best place to work. Jobs are thinner on the ground and less well paid because the economy isn't as good as the West, neither is the weather.
Do you have to go to VIC? Two years is a bit of a long look ahead. If it were more imminent, it would be easier to advise you. I used to fly with a few ex Army people on the North Sea many years ago. I liked them because they always worked hard and didn't sit around looking for excuses not to fly. There is room for people like that in Oz.