Online Archive missing in Outlook after Office ProPlus upgrade

We recently upgraded a bunch of users from Office 2013 / 2016 Professional Plus to Office 2016 ProPlus using our O365 E3 licences. A bunch of users, both on-prem and in O365, could no longer see their Online Archive in their Outlook. The online archive was gone, kaput, missing, absent, you get the idea.

Interestingly, it did show up in their Outlook Online / on-prem webmail however.

This pinpointed it to probably being their Office 2016 KMS licence key from the previous install. A check of the current licences a user had looked like:

"c:\windows\system32\cscript.exe "C:\Program Files (x86)\Microsoft Office\Office16\ospp.vbs" /dstatus"

---Processing--------------------------
---------------------------------------
PRODUCT ID: xxxxx-xxxxx-xxxxx-xxxxx
SKU ID: d450596f-894d-49e0-966a-fd39ed4c4c64
LICENSE NAME: Office 16, Office16ProPlusVL_KMS_Client edition
LICENSE DESCRIPTION: Office 16, VOLUME_KMSCLIENT channel
BETA EXPIRATION: 1/01/1601
LICENSE STATUS:  ---LICENSED---
REMAINING GRACE: 178 days  (257459 minute(s) before expiring)
Last 5 characters of installed product key: abcde
Activation Type Configuration: ALL
        KMS machine name from DNS: x.x.x.x:1688
        Activation Interval: 120 minutes
        Renewal Interval: 10080 minutes
        KMS host caching: Enabled
---------------------------------------
---------------------------------------
---Exiting----------------------------- 

Hmmm, an old licence in there. Not sure why it would cause issues, but it's not the one they should have for O365. So, delete the licences with this command, using the last 5 characters of installed product key from the above command:

"c:\windows\system32\cscript.exe "C:\Program Files (x86)\Microsoft Office\Office16\ospp.vbs" /unpkey:abcde"

Restart Outlook and provided the user has a proper E3 / E5 licence, Online Archive should be visible.