Partitioning may reverse the correlation or it may not; either way, it provides a more accurate model.

Let's do this formally. Let R, G, and T be the three variables of interest in the OP's example, corresponding to Recovery, Gender, and Treatment. Then the goal is to obtain a model of the probability of R, given T and maybe G. My assertion is that a model of the form P(R|G,T) is always going to be more accurate than a model of the form P(R|T) alone - you can't gain anything by throwing away the G variable. The accuracy can be measured in terms of the log-likelihood of the data given the model.

It is actually tautologically true that P(R|G,T) will provide a higher log-likelihood than P(R|T). The issue raised by RobinZ is that P(R|G,T) might overfit the data: the accuracy improvement achieved by including G might not justify the increase in model complexity. That will certainly happen if naive modeling methods are used, but there are ways to incorporate multiple information sources without overfitting.