We had a similar issue when we were using the A1 plus licenses and it was per-user authentication for Office entitlement.
I can't remember how we got to the bottom of it, but it was after a couple years and multiple MS calls, but in our case, we had to edit the permissions of a reg file.
We had to edit the permissions of "Computer\HKEY_CURRENT_USER\SOFTWARE\Microsoft\Windows\CurrentVersion\Internet Settings" and add "All Application Packages" (Click Locations, change to the local machine and hit check now) and give it read permissions. Restarted Office and it'd let us sign in.
Not sure if it'll work for you, but thought it may be worth sharing.