In a 33-project solution file there is one ProjectDependency which is ignored. It is a C#-project which is dependent on a C++-project (using COM-interop), so we can't use a project reference in the csproj-file.
Note that we only see this problem when using /m:2 (or higher) on the msbuild command line. But I guess that it could just be a conincidence that msbuild decides to build the C++ project first in the non-parallel case rather than it reading and respecting the dependency. We can't tell.
The solution builds perfectly fine from Visual Studio - also with Visual Studio set to do parallel builds in options dialog.
We also see this on WinXp.
We also see this with Team Build. That was actually where it was discovered.