I have been keeping up with your problem for the past couple of days and have been searching for a possible answer. Here is what I have found for you. I found this document at Blackberry.com that describes your problem with possible answers. Check that document out and see what you think. Let us know if that solves your problem.
The issue was before that I didn't have to use delete on mailbox & handheld; I've always used delete on prompt (long story short was multitasking and hit delete by mistake). I switched and it did clean out the items I didn't want.
I appreciate your taking time to locate the document and posting.