Contacts Being Recreated

We are running Exchange 2007 SP3 and most of our users are using Outlook 2007. Some of our users have smartphones, be it iPhones, Android devices, and even Blackberries using our BES server. We began noticing that the Salesforce for Outlook connector was deleting contacts in Salesforce. After much discussion with Salesforce as to why this was happening, we tracked it down to contacts changing in Outlook.

What we noticed in Outlook was that the created date for contacts was changing. All the proper information was there in the contact, it was just like the contact was deleted and recreated. Several people said it must have something to do with the phone sync, however, we've checked people that have no mobile phone sync and it is happening to them as well.

Most of my contacts now have a created date of 10/27/2012. Another on 10/29/2012, and another on 10/30/2012. I even have a few from 1/20/2013 and a couple more from 1/22/2013. I haven't added any contacts in a good 6 months and I know the 2 that show created on 1/22/2013 have been in my contact list for over a year. The 10/27/2012 contacts happen to be the same date we noticed contacts disappearing from Salesforce.

We've exhausted our resources searching for a solution. No one seems to have heard about this before. According to logs, contacts have changed even when Microsoft Outlook 2007 is not even running on a user's account, such as over a weekend. Any insight into this would be very appreciative.