We had a similar problem about a year ago, and according to support sometimes contacts loose a "marker" that tells the server they've been updated or changed, or something like that. The solution was to start new, blank, contact files and connect them up to the servers. Since we only have public contacts, and make sure that everything is stored on the server (we don't use comments or private notes), it wasn't a big deal.

Before I did this, I did an export to text of everyone's contact file as a backup, and to check against the new information, just in case someone had contacts that hadn't properly synced to the server. I was able to re-import them. Turned out nobody had more contacts listed before they started a new file than they did after, and nobody complained about missing or incorrect info, so we left it at that. Had there been problems, my plan was to import the text files and use the merge duplicates feature to make sure no data was lost.

Your mileage may vary