I am not sure if it is your application after installation that doesn't work, or if it is a dll you use as part of the installation that doesn't work?
To make a very long story, very short: new versions of the C / C++ runtimes are installed as Win32 assemblies, or side-by-side installation. This means the files will go into folders under C:\Windows\winsxs - the Win32 equivalent of the GAC, and several versions of the same file can co-exist here.
Applications compiled with Visual Studio 2005 / 2008 will put a manifest file into the binary, and this manifest specifies what side-by-side runtime version to bind to. It doesn't matter if you put the MSVCR80.dll next to your EXE or even in system32 - the manifest embedded in the EXE will load the file from C:\Windows\winsxs.
This is all "full circle". In the old days runtimes went to System32. This caused the original dll-hell: applications overwriting each other's global runtime files. To remedy all this the idea was to "isolate changes" to each application. Hence the new approach was to isolate a local copy of the runtime file next to the EXE. Now this caused an entirely new problem: how do you make sure security updates for the isolated dll was deployed? In most cases this never happened, and you had lots of applications running with local, unsafe dll's. So what to do? The decision was to introduce the second coming of dll-hell: the side-by-side assembly approach. In this approach runtimes are not local, but global - with the critical difference of supporting side-by-side installations. This way, in theory, applications can function without overwriting each other's runtime dlls.
So that was the quick summary of "how to make runtime deployment complicated". I am not positive it is still possible to do, but did you check whether you can statically link to the runtime? Sometimes old-school really is easier...