Do some due diligence at Whirlpool
http://forums.whirlpool.net.au/forum/116?g=241
I'd avoid VentraIP.
edit: I've never found a good provider of VPS services in Australia.
If you need dedicated I'd only recommend bulletproof
http://www.bulletproof.net.au/
Netrigistry are rip off artists and will find ways to screw you at every opportunity, VentraIP are arrogant pricks, Exigent have massive internal network issues they refuse to address, I could go on.