I am just going to throw this out there. To me it sounds like a Working Directory thing. You mentioned that browsing to the file works, but when you run the program without browsing first (using a constant or control wired to the call library node) it fails. One thing that I have noticed when working with external code is that browsing to a directory using any of the browsing controls actually changes LabVIEW's Working Directory. I haven't found a way to programmatically change the working directory in LabVIEW.
I didn't follow along with every step you tried, but I would suggest doing some experiments while thinking about what directory is the Working Directory. For instance, after browsing to the file (and changing the working directory) you can run your vi. Does it still work if you use a constant after doing that, say on the next execution of your program? If not, does the Working Directory change when you run your program (because of something the dll does)? You can check by clicking Browse on a path control (if you don't explicitly provide a Starting Directory, this will default to the Working Directory).
Another thing to try, does running the provided test applications work because of their location? Are they in the same directory as the file they need to access? Also, you can try adding the required path to your System PATH variable, and see if that helps.
Chances are this will either make a lightbulb go off, or I am way off base. Here's hoping for the former option!

Chris