Not sure how far the Dev's have got in tracing this down, but just come across a some info they will hopefully find useful in hunting down the bug.
Got a couple of Exchange returned e-mails which seem to have generated 2 copies of each (one with the returned item, one without). Anyhow when I hold the cursor over the "From" box, one of them states "Sent from Exchange from the Holodeck Server" this one will not delete. The second one states "Sent from Exchange from the Server" and will delete. Noting the difference here being the reference to Holodeck.
Also just self mailed a couple of test e-mails to my character which come as "Sent from [email protected]
from the Server" and will also delete.
So hope this helps in tracking down the bug.