O>А версии dll точно совпадают (те, которые подкладываются ручками и те, которые ставит vcredist.exe) ?

Совпадают. Но дело похоже в другом.

я подкладывал в виде

..\AppFolder\AppName.exe
..\AppFolder\msvcp120.dll
..\AppFolder\msvcr120.dll

а надо было в виде

..\AppFolder\AppName.exe
..\AppFolder\Microsoft.VC120.CRT\msvcp120.dll
..\AppFolder\Microsoft.VC120.CRT\msvcr120.dll

Позже поэксперементирую еще на разных системах.