I had the same problem and my problem had nothing to do with paths. One of my dll-s was written in c++ and it turnes out that if your visual studio doesn't know how to open a dll file it will say that it did not find it. What i did was locate which dll it did not find, than searched for that dll in my directories and opened it in a separate visual studio window. When trying to navigate through Solution explorer of that project, visual studio said that it cannot show what is inside and that i need some extra extensions, so that it can open those files. Surely enough, after installing the recomended extension (in my case something to do with c++) the
"This application has failed to start because xxx.dll was not found."
error miraculously dissapeared.