Random Forests (RFs) is a competitive data modeling/mining method.
An RF model has one output -- the output/prediction variable.
The naive approach to modeling multiple outputs with RFs would be to construct an RF for each output variable. So we have N independent models, and where there is correlation between output variables we will have redundant/duplicate model structure. This could be very wasteful, indeed. Also as a general rule more model variables implies a more overfit model (less generalisation). Not sure if this applies here but it probably does.
In principle we could have an RF with multiple outputs. The prediction variable is now a vector (n-tuple). The decision nodes in each decision tree are now splitting the set of target/prediction vectors based on a threshold vector, I figure this threshold is taken to be a plane in the n-dimensional space and that therefore we can determine which side of the threshold vector each of the target vectors is on.
The optimal prediction value for each side of the decision split is the mean (centroid) calculated for the vectors on each side.
Finding the optimal split point when working with single variables is trivial and computationally fast/efficient. For an n-tuple we cannot find the optimal split (or at least it becomes computationally infeasible as N increases), but we may be able to find a near optimal split using a Monte Carlo type method (or some hybrid of Monte Carlo and local gradient traversal).
Would this actually work? That is, would it just map the training pairs without generalising? Does this technique already exist under a different name?
You might also want to consider how this relates to neural nets such as Restricted Boltzmann Machines (RBMs) and Deep Belief Networks.