If Add2Exchange was working and now it's not, post here.
Occasionally we notice that the pivot folder located in Public Folders retains stale contacts; Any reason why couldn't purge it once in a while?
As long as you're not in the midst of a sync, it would be fine to purge stale data. Stale data happens on occasion but isn't generally harmful.
The best way to make sure a sync isn't running is to stop the Add2Exchange service prior to emptying the folder.