Office / Word interop fails with "Element not found" error

I'm trying to use Office interop library but whenever I try to create a new instance of Word Application class I get an exception of:

System.Runtime.InteropServices.COMException (0x80070490): 
Retrieving the COM class factory for component with CLSID {000209FF-0000-0000-C000-000000000046} failed due to the following error: 
80070490 Element not found. (Exception from HRESULT: 0x80070490).

Exception is thrown at Application object creation.

class Program
{
    static void Main(string[] args)
    {
        var application = new Microsoft.Office.Interop.Word.Application();
    }
}

Test project had latest Microsoft.Office.Interop.Word nuget package (15.0.4797.1003).

For testing purposes I've tried to do the same for Excel interop but I get similar exception (with different CLSID that is).

My computer has Office 2016 installed. I've tried reinstalling Office partially or completely but that has not helped.

I can find registry entries for the object that is mentioned in exception as not found.

Interestingly I've noticed that this problem only bothers two out of four machines I've tested it on. All of the PCs have similar configuration, the same version of Office installed (and only this version).

This issue was solved by installation of Office 2019.

It does not solve the underlying issue for somebody bound to Office 2016, but the fact that new Office version helped would suggest that it is something about broken installation. However for me even full uninstall / reinstall of Office 2016 did not help.