I use godaddy https://au.godaddy.com for all my domains, mainly email, a few people have some complaints but I have had good service, apparently they are the biggest in the world, so you gotta expect some complaints. They now have a presence in Au and can do .AU sites.
A mate a work uses them for virtual servers and has had no problems.