The deleted items folder, which is where your deleted emails go, has a size limitation.
Do you empty your deleted items folder on a regular basis?
If you do, the next time it happens, close OE and just delete the "Deleted Items.dbx" file via explorer instead of going through the uninstall-reinstall proccess. OE will automatically build a new one the next time you launch it. If the problem goes away, an item in the deleted items folder itself is most likely damaged or corrupted.
If you do not empty your deleted items folder regularly, on OE "Maintenance" tab in options, you can set it to do it automatically on exit if you like. Once your deleted items folder reaches it's capacity, it will no longer allow you to delete any more messages until you make room.
Edited by HitSquad, 06 May 2006 - 09:32 AM.