First thing I would do is delete the service book on the bb device. On the bb go to Options > Advanced Options > Service Book. Then delete all service entries, you won't be able to delete them all and you will have to delete them one by one. Once that is done, go log on the BIS site for your account and resend the service book back to the bb device. Wait 20 minutes and test. If you did not upgrade the bb device before this problem happened or you did not make any changes to the settings then it very likely the service book on the bb device has become corrupted. But of course you would only know the answer to that question.
If no joy with the service book, go to Messages > Options > Email Reconciliation and make sure that the email reconciliation option is set to "On". Also make sure the Delete On is set to Mailbox and Handheld.