There are several factors that contribute to this problem.

A) Turn off background compaction under Tools>Options>Maintenance for each identity you have, and then compact manually and frequently using;
File>Folder>Compact all.
This will make OE more stable.

B) Turn off email scanning, autoupdate, and internet filter with your antivirus software. Many antivirus products interfere with the operations of OE resulting in loss of messages. Turning off these options does not affect the ability of your antivirus software to block infections.

C) Installing updates or security patches while another process is running.  This includes OE itself and any anti-virus software that you are using.  I also recommend that you temporarily turn off your firewall during the download.

If you do lose your messages, you can try using the DBXtract program to attempt to recover the lost messages. Note that dbx files are hidden in Windows 2000 and Windows XP.
http://www.oehelp.com/DBXtract/

If you have upgraded your version of IE and OE or your OS version, and all your messages are lost, then see this article (note that the technique in the article does not apply only to the issue addressed in the article title):
OLEXP: Mail Folders, Address Book, and E-mail Messages Are Missing After You Upgrade to Microsoft Windows XP
http://support.microsoft.com/default.aspx?scid=kb;en-us;313055

If File>Import>Messages does not work, ignore the error message, which is erroneous in itself, and try one of the following techniques to get your messages back:

A) Right click on each dbx file or a selection of them and choose "Properties" and clear the read only attribute of the files. Then try File>Import>Messages again.

B) Import the dbx files individually. See the last paragraph on this page for how to do that:
http://www.oehelp.com/backup.aspx

C) As a last resort use DBXtract
http://www.oehelp.com/DBXtract/

Also see Tom Koch's help article
http://insideoe.tomsterdam.com/problems/bugs.htm#mailgone

If You are running McAfee Anti-virus Software

There have also been MANY MANY reports of McAfee's email scan and auto-update facilities corrupting Outlook Express's data folders (*.dbx) causing massive loss of email, particularly from the Inbox. If you must use this program, make sure that OE is NOT set to go directly to your Inbox when opening.
McAfee have admitted there is a problem, and is referring its users to DBXtract: http://www.mcafeehelp.com/faq.asp?docid=60743&CategoryId=269&chat

This is what McAfee now says about using Email scan:
"You don't have to worry about the e-mail scan as this is a corporate feature -requiring Outlook 2000 and a mail server such as Exchange server. Unless you meet the criteria you should make sure that it is disabled. As long as you have the Download scan and Internet filter enabled you'll be just fine as these two options effectively checks anything downloaded -including e-mails. I hope this answers your question. Remember e-mail scan is for corporate users only".
Of course they don't even mention the fact that, as long as your system scan is running, a virus will be detected when you try to open or save the file anyway.

If you are running Norton Anti-virus Software

There have also been many problems associated with the Norton E-mail scanning.  You will find that page at:
http://service4.symantec.com/SUPPORT/nav.nsf/docid/2000020716064206&src=w

Here is what they say about it:

"Disabling email protection does not leave you vulnerable to viruses and
malicious software in email. It is a separate layer of protection in addition to
Auto-Protect. Auto-Protect scans any incoming files, including email, as they
are saved to your hard drive. As long as you keep your virus definitions up to
date with LiveUpdate, and keep Auto-Protect enabled and set to scan files as
they are created or downloaded, your system is fully protected".