Potrebbe essersi danneggiato il file Posta eliminata.dbx
Vai sulla lista delle cartelle di posta, cliccane una e vedi in Proprietà il percorso del file, quindi incollalo da Esplora risorse, esclusa la parte Posta eliminata.dbx; chiudi Outlook Express ed elimina il file Posta eliminata.dbx come se fosse un file qualsiasi (con OE aperto te lo dovrebbe bloccare...).
Quindi riapri OE, elimina una mail e vedi se ti fa l'eliminazione definitiva da Svuota posta eliminata...