- The Good-Turing estimator 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.
I agree with the comment that the coupon collector problem 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.
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.
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.
The problem is not very related to the optimal stopping or search theory problems I have seen.