Our first step was to install the Platform SDK: no joy. The second step was to manually copy the DLL's required (there are actually 3 DLL's you need) from a working install to the non-working install: success!
So, what could possibly be the problem here?
No amount of searching could turn up the issue, so a ticket was opened with Intel's Premier Support. Well, we should have done this from the beginning because it appears that the compiler writers themselves know a lot about the compiler toolchain; fancy that. The (relevant) response from Intel:
c2.dll is used by the Microsoft Visual C++ compiler to perform whole-program optimization. Might it be that this "release" C library was compiled with that option? If so, you will require Visual C++ to be installed in order to build using that library.Sure enough, disabling Whole Program Optimization on the Release mode builds of the C static library solved all of our issues.
My advice is that if you know you will be linking a C library on a system with only Visual Studio Premier Partner Edition installed that you be sure that Whole Program Optimization is disabled, as otherwise Fortran programmers will not be able to use it.