This will explain a lot about reconcile and hard deletes
KB04863 - Permanent deletion of email messages in Microsoft Outlook does not reconcile to the BlackBerry smartphone
link in above KB in case you missed it
KB04853 - How to enable hard deletes on the BlackBerry Enterprise Server
I have also changed the messages state size to 1000 and it cured 99% of our issues.
The performance hit and RAM increase is almost nil on the BES box.
On Device also double check:
Make sure that Wireless Reconcile is set to On. Sometimes toggling that to off, saving it, then turning it back on.
Messages Options - Email reconciliation -
Delete on Mailbox and handheld,
wireless reconcile = Yes
On conflicts = Mailbox wins.
KB11632 - How to increase the number of email messages sent to a BlackBerry smartphone during the enterprise activation process
Also you have to select those other folders before you activate or you only get new messages in the other folders.
If using the same PIN upon activation look at this KB
KB04713 - Enable message prepopulation for all users on a BlackBerry Enterprise Server
search those KBs here BlackBerry Technical Solution Center