You may have a corrupted mail folder.  If you are lucky, it is the Deleted Items folder,
and not the folder you are trying to delete the messages from.

For a corrupted Deleted Items folder:
- Close Outlook Express.
- OE5+: Locate the file Deleted Items.dbx in the mail directory and delete it.  You can
use Start, Find (or Search), Files or Folders, "Deleted Items.dbx" to find it.  On Win2000
you need enable the display of Hidden or System files in the folder options and XP you
need to use the advanced options to find Hidden or System files.  (You can also determine
the location by looking in OE at Tools, Options, Maintenance, Store Folder.)
- Open Outlook Express again.  It will create a new empty Deleted Items.

This assumes that there is nothing in the Deleted Items folder that you need.  If you do,
instead of deleting the Delete Items.dbx file (OE5+), rename it to something else, such as
deleteold.dbx.  Then use the following program to try and recover messages from it.
http://www.oehelp.com/DBXtract/Default.aspx