RE: Sync a deleted out contact from CRM
As this Question is very old, i hope it still helps the one or the other:
My situation was i used Server-Side Sync to Sync Contacts from my CRM To my Outlook.
I deleted one Contact and was not able to get it back by sync.
As i had a Productive and Test Environment and i used Server Side Sync in Production i made the following:
* went to the Testsystem and searched for my user
* went to his Mailbox
* Approved EMail
* Test & Enable Mailbox
* THIS NOW IS THE KEY!!!: There was a popup which statened "Sync items with Exchange from this D365 Org only..." I activated this flag and pressed OK
This changed my Exchange Settings to map the Test Environment.
Now i did all theses Steps again with the Productive Environment, so it would change the settings back to my needed Environment.
Now all "deleted" contacts were synced back again.