The no errors flagged is a good start, means there is nothing severely negative in the setup.
An increasingly common problem I'm seeing is that the mail is being sent out from your site by your hosting companies mail servers but that they are not listed as 'sending mail servers' for your domain in an SPF record. This will almost certainly doom any mail from the site to the spam or delete folders.
i.e. Your site
www.mydomain.com.au is correctly set up, but the emails are being sent out by mail576.awfullybighosting.com.au. Instant Spam flag.
If any of the external email addresses you mentioned are your own test addresses/friends etc, check the spam folders.
I'd say you need to contact your hosts, outline the problem, and specifically ask for the mail logs to be checked, to see if the receiving mail servers are outright rejecting or deferring the mail.
Unfortunately, in an ecommerce/online store type environment, there is often nowhere for the bounced mail report to go.
If there's nothing in the logs, it is a problem in the site to mail server setup.
There is also the usual, make sure that 'send from known domain' is set to true, the email transport is set to what the hosting co recommends etc.