What does the warning say??? Does this happen on both machines? If only one,
it is probably a corrupt Outbox or Sent Items. If it happens on both, post
the warning message.

Do the following for the Outbox, and if the problem persists, repeat for
Sent Items after you move any messages you wish to save to a local folder
you create.

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, Win2K & Win2K3, the OE user files (DBX and WAB) are by default
marked as hidden. To view these files in Windows Explorer, you must enable
Show Hidden Files and Folders under Start | Control Panel | Folder Options
Icon | View, or in Windows Explorer | Tools | Folder Options | View.

With OE closed, find the DBX file for the folder in question {Outbox.dbx}
and delete it.  A new one will be created automatically when you open OE.

General precautions for Outlook Express:

Do not archive mail in default OE folders. They will eventually become
corrupt. 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.

After you are done, follow up by compacting your folders manually while
working *offline* and do it often.

Click on Outlook Express at the top of the folder tree so no folders are
open. Then: File | Work Offline (or double click Working Online in the
Status Bar). File | Folder | Compact all folders. Don't touch anything until
the compacting is completed.

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

In Tools | Options | Maintenance: Uncheck Compact messages in background and
leave it unchecked. {N/A if running XP/SP2}.