Drop Sam / Catherine an email at MPS (Melbourne Property Solutions)
m.p.s@bigpond.com.
They are a small 2 person agency with limited property but I found them excellent
When I moved to Melbourne in 2004 I flew in Saturday morning (having previously arranged a viewing over the internet) viewed on the Monday & decided that day the apartment was for me. I would have moved in the next day but I had a hotel room booked until the Friday!
I rented a 1 bed furnished apartment in the Paramount Building (corner Bourke & Exhibition) for $400 per week including a car park space. I had the option to sublet the carpark space for $150 pm so the rental was only really $365 per week. Oh an MPS office is in the Paramount building as well which helped!