Maximal majoritarian program under incomplete voting
We can formalize this problem as follows.  Let the propositions be numbered $1,2,\dots,n$.  We have a function $f$ that, given a subset $S \subseteq \{1,2,\dots,n\}$ of propositions, returns true or false according to whether every proposition in $S$ has majority support among the survey respondents who saw every proposition in $S$.  Define $S \subseteq \{1,2,\dots,n\}$ to be a majoritarian program if $f(T)$ is true for all $T \subseteq S$.  Now we want an algorithm that, given ability to invoke $f$, finds the largest majoritarian program $S \subseteq \{1,2,\dots,n\}$.

We will of course interpret $S$ as follows: for each $i \in S$, we take whichever side of proposition $i$ has majority support (when considered in isolation; among all survey respondents who saw $i$), and take the conjunction of all of those.  Given $S$ you can easily compute $f(S)$ from the survey responses.

Here is one natural but not necessarily optimal algorithm for this.  Basically, you grow subsets from the "bottom up".  In particular, the algorithm looks like this:

Try(S):
1. If S is not a majoritarian program, return
2. If S is larger than the largest so far, remember S as the largest so far.
3. For each i in 1+max(S) .. n:
4.     Try(S ∪ {i})


You start by invoking Try({}), and when it returns, the best subset so far is the largest majoritarian program possible.  This effectively takes small subsets and tries to grow them to become bigger, but if they don't get majority support, the search is pruned and it stops trying to grow that set.

The running time could be exponential.  If you get lucky, you could hope that it runs more efficiently than that, though I don't know if you'll be lucky.

As a heuristic, you could sort the propositions by order of polarization, from most unanimous to most controversial.  That might speed up the search, or allow you to cut off the search after a certain time limit and take the best you've seen so far (with no guarantee that it is optimal, but the hope that it might be close).