A generative model, although computationally expensive, would not suffer this problem. Essentially a generative model can run in reverse, which means that if you feed values into the output you get inputs that could explain the output. Check out "Boltzmann Machines" for an example. There are plenty of examples for the MNIST dataset of hand written digits.