There seem to be similar challenges to creating a scalable solution for finding an SO/spouse (another unsolved problem).
For example a mountaineering class at the National Outdoor Leadership School puts students who don't know each other, and might not know anything about climbing, into serious high-mountain situations for a month. At the end of the class, groups of students head off on "small group expeditions" for a few days without instructors. NOLS has an excellent safety record and students often form strong friendships.
The military is another institution that takes people who don't know each other and quickly forms bonds of trust and mutual understanding to perform under very serious conditions.
Granted--those are carefully managed situations where the people are facing shared challenges. But maybe that's what YC would need to create in order to foster an environment in which founders can build strong enough relationships to feel comfortable building companies together.
Like you said, in a constrained environment like the military, it might be possible to achieve this in a short period of time through deliberate actions. I'm not sure how much that approach would prepare potential cofounders, since they're going to be operating in a much more ambiguous and freeform environment.