Organizing and accessing contact information in Outlook.com
My contacts have started to sync again and I think I have narrowed it down to Contact Binding.
My Android phone (THL W200) has dual SIMs and you can bind contacts to a specific SIM to use as a preference when calling or SMSing.
It seems as soon as I try to bind a contact (single or all), all contact syncing stops and does not return until I delete and add the EAS account again.
Since I have stopped using the binding feature, I have had no problems with adding, modifying or deleting contact entries with 2 way sync between outlook.com and the EAS account setup on my Android.
I can only assume that there is a field that the phone modifies which outlook.com does not understand and hence fails.
Although your problems may not be exactly the same, it would be worth seeing if there are any other fields (photos, specific ringtones, etc) which are altered on the phone and subsequently breaks the syn as outlook.com does not know how to handle this extra information.