Does your connection to that server cross over from one internet provider's
equipment to another's before it reaches the server?  If so, such
connections
to port 25 are likely to be blocked to cause trouble for spammers and you
need to ask optusnet.com.au if their outgoing mail server allows you to use
some other port for outgoing mail, and if so, where to find their
instructions
for this.  Just trying all the ports is a very slow way to find out, since
there
are about 65,000 ports available, and it's unlikely that more than a few of
them will accept outgoing mail.  See if this helps:

http://www.optuszoo.com.au/help/dial/connected/windows/winmail

Also click on your Outbox and then each of the messages you see there.
If any of them show an error message instead of a message you sent,
move them to the Drafts folder or delete them.  If any of them refuse
to do either, download and install this hotfix, with Windows Mail not
running:

http://support.microsoft.com/default.aspx/kb/941090

Although it's labelled as for mail stuck in the Outbox, it also works in
other folders.

If that doesn't cure your problem, but you get error messages when
you try to send yourself a short message, click on the error messages
and copy the entire error messages to your next message.

That error is likely caused by interference from a non-compatible
antivirus. For starters, be sure its email scanning is turned off.
If no improvement, be advised that some antivirus programs are
not very compatible with Windows Mail. Which one do you have?