Hi Felicity,
a tree revomalist I used (being the cheapest by far out of 4 quotes I got to remove 3 large trees & their stumps) was Dawson's Tree Services (they are full in sured, $5mil cover). They are based at Ferntree Gully, but cover all of Melb (they did my job at Altona Nth), so you would have no problems getting them out there... I was happy with the service they provided & would highly recommend them...
You can contact them on 9720 5111 OR 9720 1864 & check out their prices...
Cheers,
MannyB.