If Reconcile Now works then it will work on it's own, it's just a matter of time. When new email arrives the status of mail will not change. Reconciliation only happens when you force it or when the BES rescans the mailbox after 15-20 minutes(could take longer) of not receiving anything new. Essentially the BES updates the properties of emails during the rescan. When emails are read/deleted/moved on the device it sends the changes to be made in a folder in that users mailbox. When emails are read/deleted/moved in Outlook the BES notices the property change and then reflects it on the device. At no point is Reconciliation ever triggered by the BES.
I asked my hosting service to look in to this and this is what they replied to me...
"We have seen this before, basically what you have to do is delete the messages and give it a minute or so before you clear the deleted items folder. If you do it too quickly the BES server doesn't get a chance to scan the mailbox and note the change in status. This will resolve your issues."
I don't know if this is going to work. I typically delete messages all day and only empty my trash a couple of times a day, but we can work on it.