Creating obligatory combinations of variables for drawing by random forest
You may want to consider gradient boosted trees rather than random forests. They're also an ensemble tree-based method, but since this method doesn't sample dimensions, it won't run in to the problem of not having a useful predictor available to split on at any particular time. 

Different implementations of GBDT have different ways of handling missing values, which will make a big difference in your case; I believe R does ternary splits which is likely to work fine.