I think I know where the issue lies, the TypeNotFoundException was correct, at least the corresponding types were not generated (as shown by Reflector), this made me thinking. More exactly there is only one generated fake-file generated per assembly lying under [buildName]\Binaries- and as both of my Assemblies faked the same Assembly (backend.dll) - this resulted most probably in a race condition - the one assembly which was built later than the other had its final shims/stubs generated; this doesn't clarify all problems though.
Anyway the reason why this doesn't show up on a regular VS build is because the assemblies are generated in their respective [assembly]\FakeAssemblies directory, not influencing any other unit test (the way it is supposed to be).
So my idea to circumvent this problem was to put ALL shims/stubs used by both test-assemblies into both .fakes-configuration-files; reflector showed that really all needed shims/stubs got generated this time, however the build failed with
Exception Message: MSBuild error 1 has ended this build.
With no more information in any (detailed) log. This problem is caused by not using a generated shim/stub-object specified in the .fakes-file (and of course this is also a problem just shown by the build server, would be too boring otherwise ;-)).
So the final solution I came up with is to put ALL code that makes use of shims/stubs into the same assembly, where only 1 .fakes-file configures the fake-Assembly.
Now it is working fine :-), but I think the MS-Dev-Team has still something to do on here, haven't tested it with TFS2013 though; gonna submit a bug anyway (as I've discovered 2 already)
Hope this helps somebody with the same problem.