Algortihm for making predictions from minimal data
If your feature set is really huge and most of the variables are strong features and can determine a class on their own, i would try to go with Logistic Regression using elastic net (probably less on the lasso and more on the ridge side, so you do not throw away features which happen to always co-occur in your dataset but not in reality).

Just be sure to only consider features that appear often enough in order to avoid overfitting. This can easily happen, when the number of examples is smaller than the number of features.

Random Forests could also be worth a try, but to my experience if the number of strong features is really great but they all occur relatively rarely, RFs underperform compared to Logistic Regression.

Btw. the fact that the user only reveals partial information might not be a problem at all as long as the information given can determine the class easily - as you said. I would just give it a try.