+1  A: 

You have to change / update the manifest resource from the dlls.

mt.exe -inputresource:dll_with_manifest.dll;#1 -out:old.manifest
mt.exe -manifest new.manifest -outputresource:dll_with_manfiest.dll;#1

Sometimes the RT_MANIFEST (type 24) resource type doesn't have the #1 index in resource table, you should use a Resource Viewer (ResourceHacker, or ResEdit) and find out the index number. I have seen cases when the manifest has the #2 index number.

Cristian Adam
I tried it - the dll seems to have no manifest. Please see the edits in my post.
RED SOFT ADAIR
+1  A: 

Your best option is to ship the needed DLLs within your applications installer package. Use at least the version that your 3rd party DLL depends on.

Microsoft offers standalone installers for its runtime DLLs (vcredits_*). The latest version for VisualStudio 2005 can be downloaded here. That is also the version that your DLL is linked against. You can silently launch the redistributable package from your installer.

As a manual workaround for already installed systems, simply apply the redist installer on the target machine.

If you choose this method, you don't need to be afraid of version conflicts, as applications depending on an older versions will be redirected to always use the most recent one.

For a better understanding you have look at this MSDN articles.

Frank Bollack
I now installed the redistributable file of Visual Studio 2005.This indeed solved he problem. I wonder that its useless to just copy the assembly directory into our \bin directory (containing all Dlls and EXEs) as we tried before.
RED SOFT ADAIR
vcredist is the best option. I have seen one case when the vcredist package has failed to install. No clue why it didn't work, I had to manually unpack the vcredist.exe file and copy the files near our executable.
Cristian Adam
But why does coping the files near my executable NOT work, whereas after installing vcredist fixes the problem ?
RED SOFT ADAIR
In my case I had only one version of CRT as dependency. With multiple versions it gets complicated.
Cristian Adam