1. [The Good-Turing estimator][1] addresses a very similar problem.

The model is that there is an unknown number of types $n$ and a probability distribution $p \in \Delta_n$. Each time you pick up a new shell, it is sampled independently from $p$. After $m$ samples, you can ask for the "probability" that a new sample will be of a hitherto-unseen type.

2. I agree with the comment that [the coupon collector problem][2] is highly related. The model is the same as described above, but we are asked to bound the stopping time (number of samples $m$) after which all types have been seen. Usually, we assume $p$ is the uniform distribution. In this case, the expected number of samples turns out to be roughly $n \log n$. Your question has a twist that we don't know $n$, so we have to do a reverse kind of calculation.

3. I would model your problem as above, and I would assume a confidence parameter $\delta$ is given. The problem is to define a stopping rule such that, for any $n$, the probability that there is still an undiscovered type when we stop is at most $\delta$. This would assume the uniform distribution.

I don't think the optimal solution is obvious, but my first thought is related to Good-Turing. I start drawing samples. At any time $t$, suppose I've seen $n_t$ different types so far and there have been $k_t$ samples since I last saw a new type. If there were at least one undiscovered type, then the chance of it coming up would have been at least $1/(n_t+1)$ on each of those trials, so a total chance of $p_t := \left(\frac{n_t}{n_t+1}\right)^{k_t} \leq e^{-k_t / (n_t + 1)}$ of having this many samples without a new observation.

So if we ever see at least $(n_t + 1) \ln(1/\delta)$ samples in a row without a new type (where $n_t$ is the number of types we've seen so far), we should be able to stop and conclude with confidence $1-\delta$ that we've seen all the types. 

4. If we don't assume the distribution is uniform, then I think you can probably modify the above to make a stopping rule of the following form: If we stop, then with confidence $1-\delta$, the total probability on unseen types is at most $\epsilon$. What I mean by confidence is that for any $n$, any $p \in \Delta_n$, and any set of types with $p$-mass at most $\epsilon$, the probability that your procedure stops before seeing one of those types is at most $\delta$. In fact, I think the new rule is to stop once we see $\frac{1}{\epsilon} \ln(1/\delta)$ samples in a row with no new types.

5. The problem is not very related to the optimal stopping or search theory problems I have seen.


  [1]: https://en.wikipedia.org/wiki/Good%E2%80%93Turing_frequency_estimation
  [2]: https://en.wikipedia.org/wiki/Coupon_collector%27s_problem
  [3]: https://en.wikipedia.org/wiki/Coupon_collector%27s_problem#Tail_estimates