Unable to load adalsql.dll error when calling `Invoke-sqlcmd`

I have VS2015 with SSDT installed, along with SSMS and the SqlServer PowerShell module (which includes the invoke-sqlcmd comand), and yet If I try to execute a query against an Azure SQL Data Warehouse like so:

invoke-sqlcmd  -Query "Select top 5 * from customer"  -ConnectionString "Server=tcp:my.database.windows.net,1433;Database=Customer;  Authentication=Active Directory Integrated; Encrypt=True; "

I get the following error:

invoke-sqlcmd : Unable to load adalsql.dll (Authentication=ActiveDirectoryIntegrated). Error code: 0x2. For more information, see
http://go.microsoft.com/fwlink/?LinkID=513072
At line:1 char:1
+ invoke-sqlcmd  -Query "Select top 5 * from vwOffer"  -ConnectionStrin ...
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    + CategoryInfo          : InvalidOperation: (:) [Invoke-Sqlcmd], SqlException
    + FullyQualifiedErrorId : SqlExectionError,Microsoft.SqlServer.Management.PowerShell.GetScriptCommand

invoke-sqlcmd :
At line:1 char:1
+ invoke-sqlcmd  -Query "Select top 5 * from vwOffer"  -ConnectionStrin ...
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    + CategoryInfo          : ParserError: (:) [Invoke-Sqlcmd], ParserException
    + FullyQualifiedErrorId : ExecutionFailureException,Microsoft.SqlServer.Management.PowerShell.GetScriptComman

If I try and install adalsql.dll directly, I get a message stating that A higher version already exists and I can see the both versions of the dll can be found here:

 C:\Windows\SysWOW64\adalsql.dll
 C:\Windows\System32\adalsql.dll

and yet, invoke-sqlcmd cant find it. Any idea how to either (A) register the existing dll so invoke-sqlcmd can find it or (B) uninstall it so that it can be re-installed?

Incidentally, I am able to use Active Directory Authenticatoin with the 32-bit SQLCMD.exe, so I know the 32 bit dll is working fine. It's just the 64 bit dll that isn't loading properly...

So, this problem vexed me as well. I'm unclear as to how it happened, but maybe it's just coincidence that it happened when I installed the latest version of SSMS. My fix was to:

1. Navigate to Add or Remove Programs

2. In the little search window type sql, or just go find: "Active Directory Authentication Library for SQL Server".

Note: This will not be in Windows' installed programs list if you have installed Visual Studio 2019. You can run the same installer by invoking MsiExec.exe /I{6BF11ECE-3CE8-4FBA-991A-1F55AA6BE5BF} from a command prompt.

3. Uninstall that little guy

4. Navigate here and download the latest ADAL library (pick x64):
   https://www.microsoft.com/en-us/download/confirmation.aspx?id=48742

5. Just for kicks, reboot

6. Your stuff should now properly load adalsql.dll!

Update #3, 2020-07-13: Installing the older version works, but is vulnerable to being clobbered by the SSMS and VS2019 installers. The reason the new version of ADAL doesn't work is because its installer fails to add a registry entry pointing to the 64-bit version of adal.dll. I added an answer below which includes the missing registry value, which you can add yourself. Once that's done, you should never need to do this dance again. - @Tullo_x86