This is a known issue and it happens to my users too. I have also experienced it on my 8800. I'm on a BES 4.1 service pack 3.
Here's the link to the article with the workaround which I've applied:- KB11860 - When the IBM Lotus Domino mail file template is replaced or refreshed, email messages cannot be deleted from the BlackBerry 8100 or 8800 smartphone
No escape from wiping and re-EA...