Note 4 contact quit syncing with Outlook
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.