This will explain alot about reconcile View Document
Dont foget kb KB04853 in that doc
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.