Been there (Melb), done that (relocated) (Score 5, Informative)

Hi, I can't find how to send you a message or email privately, so here goes... I lived in Melbourne for 4.5 years (Carlton and Kew) and am now a recruiter in Canada. I work for Hays in Calgary. Shoot me an email at matthew at area709 dot com - I've been through the whole gamut (brought my Aussie gf with me, got her PR, found her a job, etc etc) and work in recruitment so can probably steer you in the right direction in exchange for a pack of tim-tams on your arrival. :)