Originally Posted by Jameson
I believe this is set on the individual Blackberry Devices.
On the BB device, inside of Messages, click the trackwheel and a menu will appear. Scroll until you see "Options" or "Email Options" and click the trackwheel to slect it. Once here, you should see an option for "Wireless Synchronization". Change this option to "Delete on Handheld & PC."
Hope this helps.
This is typically the answer on this, but also note just how they are being deleted, if it never hits the deleted items folder, it will never be reconciled