I'm going to rewrite my original question to make it a bit clearer:
Assume I have some set $P$ with $||P|| = N$ unique elements. I also have $S$ multisets, $(m_1, ..., m_S)$, of cardinality $L$, consisting of elements in $P$ chosen with uniform probability. We call a multiset, $m_i$, 'distinguishable' if it contains at least $k$ elements, though not necessarily distinct elements, that exist in no other multiset.
What is the probability of all $M$ multisets being 'distinguishable' according to this definition?
While sampling $S$ times with replacement from the set $P$, we can state the probability of never choosing the same element twice as:
Prob( $S$ unique selections from $P$ ) = $\prod \frac{(N - i)}{N}$ for $i = 0$ to $(S - 1)$
Or equivalently, we can calculate the probability that the multiset of $S$ sampled elements contains all unique elements as:
Prob( $S$ unique selections from $P$ ) = $\prod ((1-(\frac{1}{N - i}))^{(S - 1 - i)})$ for $i = 0$ to $(S - 1)$