I would suggest change the version number in your config.daml's AddInInfo tag. Use addin manager on your VM to verify that Pro is running the same addin version that works on your development machine.
I assume you don't have Visual Studio on your VM in which case you have to add logging code to locate the source of your problems. You said that not even your logging code is being executed? Is your logging code working if you add a log entry to the Module class? For example in the Current property? Make sure that your module's autoload property is set to 'false'. If that works (i.e. logging code in the Current property) i would suggest to add Roman's Assembly Resolve handler to output any errors in the late binding to your logger.
I have created an add-in that is using cefsharp.wpf which also uses late binding, without any problems. However, depending on the 3rd party package you might have to configure the 'load' environment properly. With cefsharp i had to add some code to configure the 'late binding load' environment for cefsharp. The problem is that you don't know how your 3rd party loads its required dll or resources.
I your post above you say:
Works, but not appropriate:
- Add-In working folder e.g. C:\Users\*\AppData\Local\ESRI\ArcGISPro\AssemblyCache\{GUID}
Not knowing what your 3rd party library does, I would suggest that using the 'add-in working folder' is actually an 'appropriate' implementation. You can simply add all your 3rd party library dlls to your add-in project and make sure that the 3rd party dll's build action is set to 'Content' and 'Copy to Output' is set to Copy. Now build your add-in and start ArcGIS Pro. Once ArcGIS Pro starts it will update the "C:\Users\*\AppData\Local\ESRI\ArcGISPro\AssemblyCache\{GUID}" folder and unzip the addin file's content in this folder and you should now see you 3rd party dlls in that folder. It's possible that this will fix your problem, if it doesn't you can 'redirect' the assembly load path using Roman's code snippet.
Finally i would like to clarify that the following is Not appropriate:
Works, maybe appropriate?
- ArcGIS Pro Extensions folder C:\Program Files\ArcGIS\Pro\bin\Extensions
As Gintautas mentions if you have multiple add-ins that use the same libraries you can add them to the GAC, however, that will complicate the installation/updating of add-ins because they have to be in sync with the GAC (and the setup required to install dlls and register with the GAC).