I've found installing the VS library folders( ie: Microsoft.VC80.CRT)  inside the same folder as the dependent .exe works for loadtime DLLs.  For runtime DLLs which are in their own folder not in the .exe folder, I've only been able to make them work if I don't embed the manifest.  If you don't embed a manifest you must make sure the manifest is in the same folder as the .exe or .dll.  So if you have a myapp.exe you need to make sure myapp.exe.manifest is in the same folder.

I've tried upgrading to VS 2005 SP1 but that seems to make the problem worse for me.

HTH
Hua-Ying