Non uso imap con OL da un bel po' ma ricordo bene che è il funzionamento normale, la barratura non coincide con l'eliminazione dal server. Mi sembra di ricordare ci fosse una specifica voce di menù per eliminare definitivamente i messaggi dal server. Guarda bene i menù e cerca qualcosa come "elimina definitivamente i messaggi barrati" o simile.