Apparently Bigpond's problems relate to a recent software upgrade, and it sounds like OzEmail have a very similar problem.

A quick fix to get you back up and sending mail again is to change your SMTP server to mail.yourdomain.com. If you're on the new server you also need to check the box that says "my server requires authentication". If you're on the old server then you just need to check your mail before being able to send.

Give us a call if you need a hand.