I have found a solution (after some digging) for this problem, please note that it requires MSBuild shipped with .NET 4.5 or later.
Microsoft added the property GenerateProjectSpecificOutputFolder, which will add a subdirectory with the project name under OutDir
when set. To solve the problem above, I set the property to True in every PCL project in my solution. Since the plain .NET projects in my solution have project references to those PCLs, they will still be copied to the OutDir during the build, while the PCLs the selves are being built "in isolation".
Here's how to set the property by example (I'm including this project file instead of Microsoft.Portable.CSharp.targets):
<?xml version="1.0" encoding="utf-8"?>
<Project ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
<PropertyGroup>
<!--When building in AppHarbor, we need a project specific output folder so the assembly references don't clash with those from the plain .NET projects-->
<GenerateProjectSpecificOutputFolder>true</GenerateProjectSpecificOutputFolder>
</PropertyGroup>
<Import Project="$(MSBuildExtensionsPath32)\Microsoft\Portable\$(TargetFrameworkVersion)\Microsoft.Portable.CSharp.targets" />
</Project>