Organizing and accessing contact information in Outlook.com
"New contacts made in the phone do not sync."
In case other people still have this issue, this may be a more classic problem & not that technical at all. I would check to make sure you are creating a contact on iPhone under your O365 account not iCloud or GMail etc.
iPhones supports multiple contact lists. Your default iPhone contacts more likely isn't your O365's. It is an Apple thing, usually if you have O365, you will be using O365 contacts not iCloud or Gmail contacts as your primary contacts.
They seem to be missing some basic points in their design as they always do! That is always been my observation. Too much emphasis on aesthetic than functionality. A simple user prompt to choose which contact/calendar etc should be default when adding a new account would've done the trick.
On your iPhone, check Settings, Contacts, Default account
Also different contact accounts have different color coding so you should be able to tell if your newly added contact on iPhone is not going to O365 account by looking at what color assigned to it & compare it to your existing O365 contacts.