How to get the quick answer to the "Is there AT LEAST ONE subset that contains all given elements?" question if the set of subsets is very large?
It's possible to answer such queries in time $O(M^{1 - S/N})$, where $S$ is the size of the subset in the query, using a data structure from Ron Rivest:

Partial-Match Retrieval Algorithms.  Ronald L. Rivest.  SIAM Journal Computing, vol 5 no 1, March 1976.

Basically, you convert each set to a bitvector of length $N$, then use Rivest's partial-match queries.  This is ever so slightly faster than the naive algorithm, whose running time will be about $O(M)$ (or a bit more).



Your idea using indices is another approach that might be faster in practice, especially if most sets are much smaller than $N$.  Note that it's possible to optimize this a bit.  Your index will have, for each string $x$, a list of indices of sets that contain $x$ and the length of that list.  Now, given a set $A$, you can check for each $x \in A$ the length of the corresponding list in the index, and find the shortest such list, and enumerate all entries in that list to see if any of them are a superset of $A$.  See  also https://cstheory.stackexchange.com/q/19526/5038.  I think the worst-case running time is no better than the naive algorithm, but in practice it might perform significantly better.