Users Doing a Shift Delete?
My Pearl users were experiencing the same issue. Call to support provided the following info:
BES 4.0.x doesn't support hard deletes (user does a shift delete), BES 4.1 does - users had to change to "normal" deletes. Also - if a user deletes the items and cleans out deleted items folder in less than 20 minutes, then items will not delete. Tech said that deletion reconciliation is a low priority process and it scans through the whole mailbox looking to see if a message has moved to the deleted items folder - if the folder was emptied before this process runs, then the items are never deleted on the handheld.
Hope this helps.