How can I minimize the number of answers that are relevant to a machine learning model? Problem:

We have a fairly big database that is built up by our own users. 
The way this data is entered is by asking the users 30ish questions that all have around 12 answers (x, a, A, B, C, ..., H). The letters stand for values that we can later interpret. 

I have already tried and implemented some very basic predictors, like random forest, a small NN, a simple decision tree etc.

But all these models use the full dataset to do one final prediction. (fairly well already).

What I want to create is a system that will eliminate 7 to 10 of the possible answers a user can give at any question. This will reduce the amount of data we need to collect, store, or use to re-train future models.

I have already found several methods to decide what are the most discriminative variables in the full dataset.  Except, when a user starts filling the questions I start to get lost on what to do. None of the models I have calculate the next question given some previous information. 

It feels like I should use a Naive Bayes Classifier, but I'm not sure. Other approaches include recalculating the Gini or entropy value at every step. But as far as my knowledge goes, we can't take into account the answers given before the recalculating.
You don't need to re-train on the fly. What you're looking for is an embedded feature selection algorithm, and even more precisely, one that minimizes the number of responses required.

I think this might be one of the rare cases where genetic and evolutionary approaches are the obviously correct choice.

Genetic Programming is a technique for finding models that are simply computer programs. You generate a bunch of computer programs at random, and then breed the "better" ones together. Repeating this process over time leads to highly optimized programs.

A nice feature of GP is that it is extremely flexible when picking what to optimize. So instead of "better" meaning just "more accurate", "better" can mean the sum of accuracy and $\frac{1}{\#answers\_used}$. The algorithm works the same way, and, with carefully chosen rewards, you may be able to get the best of both worlds.

There are lots of variations on this. I would probably start with a simple toolkit like EJC, and standard, boring, genetic programming.

There are specialized techniques for things like your problem too, but you'll probably get 80% of the benefit without needing to pursue them.