Admin Managed Excel Add-in not visible in Office365 Excel

We have a Excel Web Addin, that was deployed to a group of users using the Office 365 Admin Center. But the add-in is not visible in Excel 2016 (Version 1803,Build 9126.2275, Click to Deploy) for those users.

Fiddler trace shows the following when the user tries to refresh the "Admin Managed" add-in dialog box. enter image description here

Fiddler Trace

<MessageText>User must have a mailbox for name resolution operations.</MessageText>
<ResponseCode>ErrorNameResolutionNoMailbox</ResponseCode>

I also came across this post "No add-ins currently available." when deploying add-in using Centralized Deployment

that talks about enabling Exchange. I am not sure what that really means.

So any help is appreciated in understanding the issue and resolution.

Thanks -kudlur