I post this merely as a reference for others that might end up being in the same situation and since I spent almost 3 days trying to figure out the root cause of the problem, I thought it would be a good idea to post the solution here.
My situation was as follows: I tried to build a deployment package for a .net application and got TypeLoadExceptions, FileNotFoundExceptions (regarding DLLs), Side-By-Side configuration errors, etc. once I tried to run it on a vanilla test machine.
[edit]: stackoverflow won't let me answer my own question within 8 hours of it being posted, the answer follows in ~8 hours ;)
The problem was that one of the dependency projects of my application was set to "Debug" build in the Visual Studio configuration manager, therefore the debug dll of the dependency ended up being used for release builds as well. On any development machine this was no problem after all since all debug runtimes were available.
On the vanilla test machine however only the release runtimes were present which caused so much trouble to me and gave me unmeaning exceptions that lead me to so many wrong directions via google, etc.
In my case it was SlimDX that was set to build a debug build in the VS configuration manager, even when doing release builds. Since SlimDX makes use of the VC runtimes I got the above problem, but this could happen with any .net assembly that uses the VC runtimes.
I hope this will eventually safe someone some hours ;)