Power Platform | Office 365 Outlook Connector | REST API is not yet supported for this mailbox

Other while importing a solution from market place, I had to create a Office 365 Outlook connection to complete the setup. However got following “REST API is not yet supported for this mailbox” error while creating the connection. Reason and fix: Error could be of 2 reasons 🙂