Another host to consider with AU presence (both Sydney and Melbourne) is Vultr.

Not associated, but have been using them for some personal infrastructure lately - it's a really nice platform. If you have strong isolation requirements they have bare metal options too.