"We can't check to see if the recipients are in Dynamics 365 because you don't have sufficient privileges" when accessing the Dynamics 365 App for Outlook

When you click the Dynamics 365 app in Outlook (anywhere the app is supported) and your Dynamics 365 (online) instance is version 9.x, you see the following message:

"We can't check to see if the recipients are in Dynamics 365 because you don't have sufficient privileges"

This error can occur if your Dynamics 365 security role does not have global read access to the Contacts entity.

1. Access Dynamics 365 as a user with the System Administrator role.
2. Navigate to Settings and then click Security.
3. Click Security Roles.
4. Select your user security role (out of the box it is Dynamics 365 App for Outlook User).
5. Open Core Records tab and check that Contact entity has read privilege enabled.
6. Try to open Dynamics 365 App for Outlook again.