Another common BlackBerry question I get is regarding deletion of messages. I could probably write a whole novel about all the different issues you can run into with BlackBerry synchronization but I’ll spare you the pain and just mention a few things.
When people hold the shift key down and hit delete to permanently delete items in their Outlook it doesn’t give the BES server (BlackBerry Enterprise Server) time to process the deletion so the deletion doesn’t synchronize and in turn your BlackBerry still shows the message as available. How do you fix this? You need to turn on “Hard Deletions” in your BES server. What this does is it allows the BES server to process the shift-deletion of emails so they synchronize properly.
You can do this by following the instructions at this Blackberry Knowledgebase Article Doc ID KB14142.