DLL not registered when connecting to the computer

I'm migrating a VSTO OUTLOOK add-in from 32-bit to 64-bit. It works well on Office 2007 32-bit. The goal is to make it run on Office 365 64-bit.

I have recompiled the add-in for a 64-bit plateform and updated the installshield project.

When I install the add-in on a new Windows 10 machine using my account (I have admin privilege), it works fine. I can see it in Outlook and I can use it.

However, if I log out and ask someone else to log in on the save machine (this someone else also has admin privilege), the add-in shows up in Outlook but this error is shown when the user uses it:

System.Runtime.InteropServices.COMException (0x80040154): Retrieving the COM class factory for component with CLSID {29AB7A12-B531-450E-8F7A-EA94C2F3C05F} failed due to the following error: 80040154 Class not registered (Exception from HRESULT: 0x80040154 (REGDB_E_CLASSNOTREG)).

Any idea?

Details:

This add-in uses only one external DLL: a 64-bit DLL from Redemption.
The solution has been compiled in Visual Studio 2015. Platform target: x64.
To install it on a computer, I use a MSI that I've created using InstallShield Express on Visual Studio 2015.
In InstallShield, I have specified ALLUSERS-1 (Per-machine installation).
The DLL is registered using the following code:

Dim WshShell

Set WshShell = CreateObject("Wscript.Shell")

WshShell.run "regsvr32 /s ""C:\Program Files (x86)\MyCompany\AddInName\Redemption64.dll"

Set WshShell = nothing

Actual Steps: Just an attempted, pragmatic summary on top: 1: Whilst logged in as the second user, try to launch regedit.exe and export HKCR (maybe HKCU as well), then register the COM dll, export again and diff with a suitable diff tool (if the launching worked at all that is). 2: Download ProcMon.exe and monitor your application / add-in launch to determine what is going on. 3: Use Visual Studio and step-through and checking the Modules view to determine what is going on during launch. 4: Use oleview.exe to see what registration the COM file requires (open embedded typelib). File => View Typelib.... More details below.

Quick Check: Maybe check this first: Outlook Redemption - using RedemptionLoader without regsvr32 the DLL.

Also, did you shut down everything before the second user logged on? Or did you just switch users? Maybe try both, make sure your first login has nothing loaded or locked.

The below "registration debugging" might miss the target. It looks like this could be something more peculiar. Maybe just skim it.

Deployment Mnemonic: Maybe try this deployment mnemonic. A little paragraph with reminders how you can think to try to solve deployment problems: "What is locking, what is blocking, what is missing, etc..."

Registration: Though this looks like a simple missing registration, it could be something more peculiar. I have this application launch check list that you can skim. Not written for add-ins, but might give you some ideas.

regsvr32.exe: Did you try to run regsvr32.exe manually as the second user to check if that works? Though it is possible to register a COM file per-user, I don't know of a way to use regsvr32.exe to do so that is reliable.
ProcMon.exe: Are you familiar with using ProcMon.exe? Her is a rudimentary example. And Hanselman showing how it is done (YouTube). You can use that to try to determine what is failing and when. Needs some practice to use effectively, but it is my "first and last resort".
Visual Studio: I like to use Visual Studio to step through the code and look in different windows (modules for example) to understand how the application works and hence to determine what can be wrong during launching.
oleview.exe: To figure out what a COM-file registers during self-registration there are several ways. Launching oleview.exe with admin rights and then going File => View Typelib... and then locating the COM file you want to check and opening gives you the embedded IDL details.
RegSpy2.exe: Alternatively you can use RegSpy2.exe for COM registration extraction. See sample here.
Capture Compare: Finally a setup capture tool can be used for debugging. It scans the registry (and disk) for before and after changes. In other words you make a baseline, register the dlls and then scan for differences. The reliable tools are expensive (AdminStudio, Advanced Installer Architecht, etc...). The poor man's version of a setup or registration capture is to export HKCR before and after using regedit.exe, and then diffing with a file/text-diff tool.

Self-Registration: Self-registration is not recommended for COM registration as described here: MSI register dll - Self-Registration considered harmful. In Installshield you can simply register a COM file by extracting the COM data at build as illustrated in the image below. You can also enable COM-Interop registration in the same list by setting the flag ".NET COM Interop" to yes:

COM Interop: .NET assemblies can be registered for COM use using regasm.exe. That is (almost) the same as the .NET COM Interop setting mentioned above set to "yes". If you want to use a COM file from .NET you need to generate an Interop assembly file and then installing and registering the real COM file (which you do). Both operations must be performed.

Throwing in a couple of links. These (ancient) articles deal with the use of regasm.exe, tlbexp.exe, tlbimp.exe and gacutil.exe. Not needed for you, but leaving in for reference:

Calling COM Components from .NET Clients
Calling a .NET Component from a COM Component

Some Links:

Registering COM EXE with WIX
Registering a CPP dll into COM after installation using Wix Msi installer
Application is not getting opened after installing it with the installer created by "Visual studio installer"