ok, so getting the picture now
If you are replicating to non default contact folders, where all the items in the destination came from A2E relationships as copies, one (Free) way is to manually delete those items copied from those folders, recreate the relationships and let it sync.
If they are to folders where other items are made, you cant delete only the copies, but A2E Toolbox Startover can. You will have to license this or have us do it under Remote support. ONLY do this if you absolutely know the relationships you have now - Open the Add2Exchange Console and Help Export the setup and print it out. Then delete all the relationships as you did already and then empty the trash from the global options. Doing this will not allow A2E to clean up after itself normally and you will have destination copied items there because of your unique situation. Then let it run a full sync.
Then open the Console and make the same relationships again. Be very careful to make exactly the same relationships (to the new folder) as you did before. Then close the A2E Console, open the Toolbox and license it. Buy Now Then run the Startover. It will remove all the copies and then use this procedure to complete. We can do this for you if you wish: http://guides.diditbetter.com/a2e-guide/upgrade_add2exchange.htm