Outlook Android no longer synchronizes Office 365 contacts
Well, it seems, they restructured how the contacts are synchronized.

I checked my Outlook on my computer, and it has 2 separate contact store options:


  Address book - mycompanyemail@mycompany.com
  
  Contacts - mycompanyemail@mycompany.com


All my company coworkers were in the Address book and my Contacts were empty.

I copied them to Contacts and now they are all synchronized - even appear in the new Contacts tab of Outlook Android.

So to draw a lesson: always check your online Contacts and see what it contains.