I have a Note 4 running Marshmallow that suddenly stopped syncing contacts with Outlook, with no changes to the exchange account or Outlook app (that I know of). I have researched this and tried all the fixes I've found, i.e. making sure it's set to display the right contacts (tried all and the outlook service), making sure syncing is enabled (it is), and deleting the account from the Outlook web UI, restarting the phone, and resyncing. Nothing works. I found one post that said this could be caused by an invalid entry from the phone in contacts, but the instructions it gave for looking at the logs on the outlook webapp were from an older version and I can't figure out how to do it on the latest one. Can anyone tell me how to troubleshoot this?
Try this tool for testing whether the problem is in your Note 4 or in the exchange: http://www.akruto.com/best-ways-to-sync-android-with-microsoft-outlook/
This should work at least for identifying the source of the problem. If you would sync your smartphone with Outlook using this software then it means that the problem is somewhere inside of exchange settings. If this software would act just like your current connection, try to check for special characters and the like in your address book.