Symptoms
After Office 365 upgrade, Sales Order and corresponding Provisioning "Subscription" task fails with:
Azure AD GRAPH API Error: 'The identity of the calling application could not be established.'.
In the Office 365 sitelog the following message appears:
ERROR aps_endpoint: Azure AD Graph API server returned an web exception 'The remote server returned an error: (401) Unauthorized.'.
Cause
During the Office 365 upgrade, step 2.4:"Configure pre-consent for the native app" from the Upgrade Knowledge Base article was missed.
Resolution
Follow the steps from the KB article #126807 for all Office 365 instances.
Also, according to Office 365 documentation make sure that two separate native applications configured in the instance settings: the first for the Partner Center API, the second for the Graph API.