You mean they don't delete as in they are there but with a strikethrough in the subject, or they are there as "new mail"? If it's a strikethrough issue, then compact the folder. If not, can you give us the system specs (mail server & version, OS & version) ?