Add-ins do not appear in Admin Managed after deploying in the Office 365 admin center

After deploying a Word add-in through centralized deployment, it doesn't appear in Word. We used this procedure to deploy the add-in and it lists it there successfully.

Since we were worried that this might be due to something awkward with our own plugin, we decided to try deploying the Contoso Citations plugin, which is used in the same procedure and screenshots here .

After capturing traffic, when we click "Refresh" in the Add-in Administrator dialog box, we noticed a connection to Exchange. Then we captured traffic using a proxy and some root certificates and we found the following call:

POST https://outlook.office365.com/ews/exchange.asmx

<s:Envelope xmlns:s="http://schemas.xmlsoap.org/soap/envelope/">
  <s:Header>
     <RequestServerVersion Version="V2016_10_10" xmlns="http://schemas.microsoft.com/exchange/services/2006/types"/>
     <MailboxCulture xmlns="http://schemas.microsoft.com/exchange/services/2006/types">en-US</MailboxCulture>
  </s:Header>
  <s:Body>
    <GetPrivateCatalogAddIns xmlns="http://schemas.microsoft.com/exchange/services/2006/messages"><Client Code="Win32_Word" Version="16.0.0.0"/></GetPrivateCatalogAddIns>
  </s:Body>
</s:Envelope>

      

        
        
        
      

    

Which seems to be pulling a directory from Exchange. For some reason, 500 appears to be returned with the following response:

<?xml version="1.0" encoding="utf-8"?>
<s:Envelope xmlns:s="http://schemas.xmlsoap.org/soap/envelope/">
    <s:Header>
        <Action s:mustUnderstand="1" xmlns="http://schemas.microsoft.com/ws/2005/05/addressing/none">*</Action>
    </s:Header>
    <s:Body>
        <s:Fault>
            <faultcode xmlns:a="http://schemas.microsoft.com/exchange/services/2006/types">a:ErrorInternalServerError</faultcode>
            <faultstring xml:lang="en-US">An internal server error occurred. The operation failed.</faultstring>
            <detail>
                <e:ResponseCode xmlns:e="http://schemas.microsoft.com/exchange/services/2006/errors">ErrorInternalServerError</e:ResponseCode>
                <e:Message xmlns:e="http://schemas.microsoft.com/exchange/services/2006/errors">An internal server error occurred. The operation failed.</e:Message>
            </detail>
        </s:Fault>
    </s:Body>
</s:Envelope>

      

        
        
        
      

    

However, no error dialog is displayed. It just shows "No add-ons available". We are running different versions of Office 365 ProPlus (Build 1704, 1703, and a few others), but all seem to result in a 500 result. We have also enabled OAuth authentication on our Exchange mailboxes. Removing all of our plugins from the Office 365 admin center still results in 500s.

Does anyone know why Exchange might throw us 500, how can we get around this and still deploy the add-in using the Office 365 admin center? Unfortunately, deployment using SharePoint or Shared Folders is not possible, and our add-in should not be deployed using storage.