If your using Outlook 2003 in conjunction with an Exchange server configured
to retain deleted items, you can recover items not put in the Deleted Items
folder. This article cites Exchange 5.5/2000, but it also works with Exchange
2003 and Outlook 2003:
http://support.microsoft.com/kb/178630
Basically, you need to create a DWORD registry value called DumpsterAlwaysOn
under the following key, and assign it a value of 1:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Exchange\Client\Options
I don't know if there's an equivalent capability for Outlook not used in
conjunction with an Exchange server.