D365FO: Microsoft Dynamics Office Add-in license information error

Got an unusual Microsoft Dynamics Office Add-in error some time ago on one of the newly created D365FO LCS machines: "The license information for this add-in is missing or expired, so it may have limited functionality."

There was a user with correct Office 365 license logged in to Excel. The add-in itself does not require any special license and works fine on many other VMs with the same settings.

The solution was to delete Office add-in via Insert -> My add-ins -> Office add-ins:

And then install the same add-in again from Microsoft AppSource.