If you have a Blackberry that is connected to a Blackberry Enterprise Server, and you are having an issue with emails between the mailbox and device being deleted, there are a few steps you can take to determine if it is Outlook that is causing the issue (It usually is).
First Step: Send Three Emails to the Outlook Client - Read One, Delete one without reading, and Delete one after reading. Then check the blackberry. If it's not the same, proceed to the next step, if you can.
Second Step: Log into Outlook Web Access (OWA) and do the same as above. Then the check the Blackberry again. If it is the same, the issue is with Outlook.
If the issue is with Outlook, remove any running add-ins and try again from Outlook, if that works you are good to go! If not, repair Outlook and that should do the trick.
If the issue is NOT with outlook, try this. Go into the preferences of the BES Server and raise the "Message State Size" to 1000. Sometimes this fixes the issue.
If none of these work, please post a comment! I'd like to find any other solutions that work as well!
(In these cases, the Outlook Clients were 2007 and 2010)