I've had this same dependency problem and I also know that you can include the VS 8.0 DLLs (release only! not debug!---and your program has to be release, too) in a folder of the appropriate name, in the parent folder with your .exe:
How to: Deploy using XCopy (MSDN)
Also note that things are guaranteed to go awry if you need to have C++ and C code in the same statically linked .exe because you will get linker conflicts that can only be resolved by ignoring the correct libXXX.lib and then linking dynamically (DLLs).
Lastly, with a different toolset (VC++ 6.0) things "just work", since Windows 2000 and above have the correct DLLs installed.