IMO nobody's comparable to the likes of AWS / Linode / Rackspace Cloud in Australia. There are some bigger players, but if you're not at the "several racks" stage, you're usually dealing with 2-3 man shops, or with a retail DSL provider which has a 2-3 man "business hosting" team off on the side. My friend spun a VM up at Australia's second-largest ISP and the customer service people told him they'd fix it within 14 days after it "ran out of space" (it was a "20 gig disk" VM which he'd barely touched).
Did I mention expensive?
Several people are selling white-label VMWare cloud stuff, so I guess you could get a persistent API before today, but in all other regards someone both as accessible and competent as Amazon is a big win for us down here.
EDIT: 30% premium over Eastern US (Virginia) for the standard instance types. 23% for a reserved instance you'll run for a year. Other instance types range from 12% - 30% over Virginia.