I think I have a similar problem. I have Outlook 2016, using MAPI and an Android phone using EAS. If I update a contact on Outlook (MAPI), the Outlook status bar just keeps flashing back and forth "Updateing firstname.lastname@example.org Updating This Folder Connected to Microsoft Exchange".
Once I saw this post, I disconnected other clients and shut down the phone and Outlook. I then started Outlook again, and it did finally sync the contact, as it showed up in the web interface. Both Outlook and the phone were added way after going to 7503.