Based on your original post, I am assuming you have already done the following:
Tools > Options > Email Options > Checked the "Save copies of messages in Sent Items folder" option
If that is the case, you may have a problem with your Outlook profile. Since Outlook allows you to create more than one mail profile, why don't we leave your current profile alone and create an additional profile for testing? If the new profile works properly, we can migrate your Outlook items in the next step.
First make sure Outlook is closed, then open the "Mail" setup utility in the Windows Control Panel. Click "Show Profiles," then "Add." Enter a name for the new profile, like "OptusNet," and click OK. Instead of having Outlook automatically determine your settings, check the box next to "Manually configure server settings or additional server types" and click Next. Enter your name and email address, set the account type to "POP3," set the incoming and outgoing mailserver names to "mail.optusnet.com.au", enter your email username and password, check the "Remember password" box, then click on "More Settings." Change the Mail Account name to something like "OptusNet Mail." Click on the "Outgoing Server" tab and place a check in the box next to "My outgoing server (SMTP) requires authentication" and "Use the same settings as my incoming mail server." Click OK. Click on "Test Account Settings" to make sure you entered the settings properly. If so, go ahead and click Next and Finish. You should now be back at the "Mail" dialog box. Click on the "Prompt for a profile to be used" radio button and select OK to finish the profile setup.
Now go ahead and restart Outlook, making sure to select the new "OptusNet" profile when prompted. First, make sure that "Save copies of messages in Sent Items folder" is checked by going to Tools, Options, then Email Options. Next, fire off an email and see if a copy was stored in the Sent Items folder.
If all is well, let me know and I'll help you migrate the Outlook data from the old profile into the new one. After that, all you have to do is delete the old profile.
Hope this helps!
Hillyman