After some recommendations for Australian VoIP provider with some key features:
- call recording
- auto attendant (or greeting before call is connected)
- Fax to email & email to fax

Did look at 2talk, but there are some issues around caller ID and dial plan etc.