To address the issue, I first fully removed the Office365 / 'Microsoft Exchange ActiveSync' account at the 'settings' / 'accounts and backup' / 'manage accounts' screen (choosing 'remove account' from within the account entry). I then re-added the account in the same area, using the 'add account' option, and then choosing 'microsoft exchange ActiveSync' option. Once added, I verified that 'sync on for all items' was shown for this account. NOTE - removing and re-adding the account caused some orphan contacts that were in the phone but not office 365 to be deleted, so be warned.
I then went to the phone app, 'recents' list, and chose an unsaved number from the list; I then chose 'add to contacts', 'create new contact'. THIS IS THE IMPORTANT BIT ... the option is presented to 'save contact to', and it offers (in my case) 'Phone', 'Google', 'Microsoft Exchange Active Sync' (the list of options will reflect the number of accounts you have configured on your phone). It also has choices for 'just once' and 'always'.
At this point, before proceeding, I wanted to discuss this screen. In my mind, if you have a 'sync' solution for contacts, you should only ever have to 'save' a contact to the 'phone', since that's what 'sync' is there for - to sync the phone to whatever outside services you may have. You shouldn't be asked if you want to 'save contact to' (eg) Exchange ActiveSync. But if you in fact choose to save the contact to 'phone', what I believe this means is, save contact to phone ONLY and DO NOT SYNC (even though you've elsewhere told the phone to sync contacts!). And if you choose to 'save contact to' Exchange ActiveSync, you are actually telling the phone to save the contact to the phone, and also sync the contact to Exchange ActiveSync. This further implies you can only sync contacts with one outside account, despite having multiple accounts configured on the phone.
Secondly, and still on this screen, the choices of 'just once' and 'always' are crucial. If you choose 'just once', you get to make the same choices next time you try to save a contact (and could choose to save / sync the contact to a different account), but if you choose 'always', that's it - you will never be asked again (until you delete the accounts, or some other 'reset' condition that I'm not aware of).
So - if you choose 'phone' as the 'save contact to' location, and assume (incorrectly) that sync will occur thanks to having chosen to sync contacts elsewhere, and then choose 'always', you will forever be saving contacts ONLY to the phone and sync will never occur again!
I chose 'save contact to' / 'microsoft exchange activesync' / always, and now everything is working as expected again ... but I feel that the logic behind this setup is a bit dubious.
Also, as an aside, during my experimenting I tried adding the office 365 mail account a totally different way, and 'things worked' but appeared differently. Instead of adding back the office 365 account using settings / accounts and backup / 'manage accounts', I used the Android Outlook App, and chose to configure the mail account there. In this case, when in the phone contacts app, and choosing to save the contact, the 'save contact to' screen showed the account as 'Outlook', not 'Microsoft Exchange ActiveSync' (same exact mail account).
