Re: Clicked on Exchange Options and unchecked Sync Contacts. I synced the account with the server. Then I went back into those same settings and checked Sync Contacts. That worked.
Right, that removed all synced contacts from the device and re-synced again (just the ones that were still there).
But the usual incremental sync should have worked too.
For the record, I just tried it -- deleted a contact in Office 365, waited for Aqua to sync the change, and it did delete the contacts from the device's Contacts... There may still be an issue somewhere, but I'm unable to reproduce...