Linking statically will bloat all your EXEs and DLLs, and can cause crashes (eg. if code in one DLL calls free() with a pointer allocated by malloc() in a different DLL).
You can get the best of both worlds by linking dynamically and deploying the runtime DLLs as private assemblies. This simply means putting a copy of a specially-named directory containing the runtime DLLs and their manifests next to your executable.
See the section “Deploying Visual C++ library DLLs as private assemblies” at http://msdn.microsoft.com/en-us/library/ms235291(VS.80).aspx for details, but basically your application looks like this:
c:\Program Files\My App\MyApp.exe
c:\Program Files\My App\MyLibrary.dll
c:\Program Files\My App\Microsoft.VC80.CRT\Microsoft.VC80.CRT.manifest
c:\Program Files\My App\Microsoft.VC80.CRT\msvcr80.dll
As to your last question, yes, the target machine needs the correct versions of the runtime DLLs to work, but by deploying them as private assemblies, you guarantee that.
Another benefit is that non-admin users can install your app (not into Program Files, but elsewhere) – they don’t need permission to write files into the WinSxS area.