Modeling and Predicting Co-Occuring Values
I would recommend a Restricted Boltzmann machine, which is a type of neural network that can model probability distributions. What you are trying to do is to estimate the marginal distribution of the missing features. In a probabilistic model, this is done through marginalization. The beauty of this method is that it provides the full distribution over the missing features rather than mere point estimates.

Here are two tutorials.