Android version 6.0 not correctly syncing outlook contacts
I had the same problem and got in touch with support.

They said the app was design like this. You can show your contacts in Android but they are read only.

Unfortunately some apps don't play well this rule and make were think it will sync a new contact to cloud. Believe me, it won't.

I'm still trying to find an alternative but in Outlook there is no way.