| | Found a solution (worked for me)
I have the 7250 with BES 4.0.1 and was having the same issues with mail not being deleted from Exchange.
I found that if you do the following it will sync:
Open mail icon
select message (any one)
Scroll down to Options and select
Select Email Reconciliation
Select the Delete on field
Select Change Option
Change it to Mailbox & Handheld
Give it a try.