First thing you need to check, go to bb device, go to your mail, select Options > Email Recon. Under that the setting Delete On should be set to Mailbox and Handheld. The other setting to look at is Wireless Reconcile, this should be set to On. If after that it is still and issue from the BES server, resend the service book to the bb device, wait 20 minutes and test.