Different tactics then.

The two most common reasons for what you describe is disruption of the
compacting process, (never touch anything until it's finished), or bloated
folders. More on that below.

Why does OE insist on compacting folders when I close it?:
http://www.insideoe.com/faqs/why.htm#compact

Why Mail Disappears:
http://www.insideoe.com/problems/bugs.htm#mailgone

About File Corruption:
http://www.microsoft.com/windows/IE/community/columns/filecorruption.mspx

Recovery tools:

If you are running XP/SP2, and are fully patched, then you should have a
backup of your dbx files in the Recycle Bin, (or possibly the message
store), copied as bak files.

To restore a bak folder to the message store folder, first find the location
of the Message Store.

Tools | Options | Maintenance | Store Folder will reveal the location of
your Outlook Express files. Press the Tab key to highlight the folder
location, then Ctrl+C. Close OE, then Start | Run | Ctrl+V will put the
location in the box - Click OK and you'll see the OE files. Otherwise, write
the location down and navigate to it in Windows Explorer.

In WinXP, the .dbx files are by default marked as hidden. To view these
files in Explorer, you must enable Show Hidden Files and Folders under Start

Close OE and then in Windows Explorer, click on the dbx file for the
missing, or empty, folder and drag it to the Desktop. It can be deleted
later once you have successfully restored the bak file. Minimize the Message
Store.

Open OE and, if the folder is missing, create a folder with the *exact* same
name as the bak file you want to restore but without the .bak. Eg: If the
file is Saved.bak, the new folder should be named Saved. Open the new folder
and then close OE. If the folder is there, but just empty, continue on to
the next step.

First, check if there is a bak file already in the message store. If there
is, and you removed the dbx file, go ahead and rename it to dbx.

If it isn't already in the message store, open the Recycle bin and right
click on the bak file for the folder in question and click Restore. Open the
message store back up and change the file extension from .bak to .dbx. Close
the message store and open OE. The messages should now be back in the
folder.

If the messages are successfully restored, you can go ahead and delete the
old dbx file that you moved to the Desktop.

If you do not have bak copies of your dbx files in the Recycle Bin, then:

DBXpress run in Extract From Disk Mode is the best chance to recover
messages:
http://www.oehelp.com/DBXpress/Default.aspx

And see:
http://www.oehelp.com/OETips.aspx#4

A general warning to help avoid this in the future:

Do not archive mail in default OE folders. They will eventually become
corrupted. Create your own user defined folders for storing mail and move
your mail to them. Empty Deleted Items folder regularly. Keep user created
folders under 100MB, and Default folders as empty as is feasible.

Turn off e-mail scanning in your anti-virus program. It is a redundant layer
of protection that eats up CPUs, slows down sending and receiving, and
causes a multitude of problems such as time-outs, account setting changes
and has even been responsible for lose of messages. Your up-to-date A/V
program will continue to protect you sufficiently. For more, see:
http://www.oehelp.com/OETips.aspx#3

And backup often.

Backup and Restore:

http://www.insideoutlookexpress.com/backup/

http://www.oehelp.com/backup.aspx

And this good one click backup program.

Outlook Express Quick Backup (OEQB):

http://www.oehelp.com/OEBackup/Default.aspx