Q:

How can an EXE have static dependency on a DLL?

Often when trying to run an EXE which uses a DLL, if the DLL is missing you get a standard Windows error:

The program can't start because
  XXX.dll is missing from your computer.
  Try reinstalling the program to fix
  this problem.

This seems to be built-in to the EXE before any of your code gets called... how does it work, and how does this get set up when building a project in Visual Studio? 
edit:
In my specific scenario I actually have a DLL which has "static" dependencies on other DLLs so if those aren't present, registering my DLL fails which is a little hard to diagnose. But I'd rather not manually list ever DLL function used as there are lots!

A:

When you link to a DLL there are two ways to do this, implicit linking and explicit linking.  What you are encountering is a failure of implicit linking.
Implicit linking operates through something called the import table contained in the executable image which uses the PE (Portable Executable) format. The PE format defines both import and export tables. The export table contains the list of functions exported by a DLL, and their entry points. The import table contains the implicit dependencies on other modules.
When an executable starts the loader reads the import table and then tries to load all the DLLs referenced and all the functions in those DLLs. This can fail if the DLL is not found, if the DLL fails to load properly, or if the DLL does not contain the referenced functions. In your case it is failing because the loader did not find XXX.dll in the DLL search path.
The linker will generate the import table. In C++ this is typically done via the .lib file for that DLL.
Explicit linking is where your code calls LoadLibrary and GetProcAddress to load a DLL and its functions. Typically this approach is used when you want to write an app that can run on different systems. For example you may wish to use certain functions that are only present on certain versions of the OS, but degrade to some other behaviour when run on an older version of the OS.
The term static should not be used when referring to linking to DLLs. Static linking is when the implementation of a function is included in an image rather than contained in an external library.
The MSDN article on the topic explains all this and more.

