They appear to be a trusted name in (big) business circles, and have been around since the beginning of the Internet in Australia.

I guess you have to pick your poison, a company that might not be so great but has been around, or someone that is great but fleeting. Although that is starting to change now with Linode, Rackspace, and others.