Suppose 4 events are observed with frequency vector $c=(1,1,2)$ as in @quasi 's example and that there are really 5 unique objects labeled A, B, C, D, and E. The probability of observing one A, two D's, and one E is given by the multinomial probability mass function:
$$\text{multinomial} = \frac{4! \left(\frac{1}{5}\right)^4}{1! 0! 0! 2! 1!}=\frac{12}{625}$$
But because we don't know if we've seen A, D, and E or B, C, and D or A, B, and E, etc. we need to multiply that probability by the number of possible arrangements of the selected objects. To do so we look at the frequency of the frequencies. We have the "true" frequencies of (1, 1, 2, 0, 0). There are 2 objects with frequency 1 and 1 object with frequency 2, and 2 objects with frequency 0. That frequency of frequency vector is $f = (2,1,2)$. The possible number of arrangements is
$$\text{multiplier} = \frac{5!}{2! 1! 2!}=30$$
So the probability of the observed frequencies $c=(1,1,2)$ is multinomial*multiplier = (12/625)*30 = 72/125 = 0.576.
You go through this process for $n = 3, 4, 5, 6, \ldots$ and choose the value of $n$ that maximizes the probability of the observed frequencies.
Some Mathematica code to do this for a proposed set of observed frequencies follows:
prob[c_] := (Total[c]!/((c!) /. List -> Times)) (1/Length[c])^Total[c] *
(Length[c]!/((Tally[c][[All, 2]]!) /. List -> Times))
{3, prob[{1, 1, 2}] // N}
(* {3, 0.444444} *)
{4, prob[{1, 1, 2, 0}] // N}
(* {4, 0.5625} *)
{5, prob[{1, 1, 2, 0, 0}] // N}
(* {5, 0.576} *)
{6, prob[{1, 1, 2, 0, 0, 0}] // N}
(* {6, 0.555556} *)
{7, prob[{1, 1, 2, 0, 0, 0, 0}] // N}
(* {7, 0.524781} *)
{8, prob[{1, 1, 2, 0, 0, 0, 0, 0}] // N}
(* {8, 0.492188} *)
We see that $n=5$ maximizes probability of observing $c=(1,1,2)$.
That is the process for determinine the maximum likelihood estimate given a particular set of observed frequencies. What is also important is knowing the distribution of the maximum likelihood estimator given the sample size ($m$) and the number of unique elements in the population ($n$).
Because the maximum likelihood estimate is $\infty$ when all of the observed frequencies are 1, the maximum likelihood estimator has no mean and therefore can't be unbiased (as you mentioned that unbiasedness was important to you). That doesn't mean that there aren't unbiased estimators but just that using maximum likelihood won't achieve that.
Here is some Mathematica code to obtain the distribution of the maximum likelihood estimator of $n$ given the sample size $m$. First, define a few functions to obtain the possible samples, probabilities, and maximum likelihood estimates:
(* List of possible observed frequencies given sample size and number of items in population *)
ss[m_, n_] :=
If[Length[#] < n, Join[#, ConstantArray[0, n - Length[#]]], #] & /@ IntegerPartitions[m, {1, n}]
(* Probability of observing a particular set of n frequencies *)
prob[c_] := (Total[c]!/((c!) /. List -> Times)) (1/Length[c])^Total[c] *
(Length[c]!/((Tally[c][[All, 2]]!) /. List -> Times))
(* Maximum likelihood estimate of n given observed frequency counts *)
mle[c_] := Module[{n0},
n0 = Length[c];
If[Total[c] == Length[c], \[Infinity],
Sort[Join[{{n0, prob[c] // N}},
Table[{i, prob[Join[c, ConstantArray[0, i - n0]]] // N}, {i, n0 + 1, 500}]],
#1[[2]] > #2[[2]] &][[1, 1]]]]
(Note that the mle
function only allows a maximum value of $n$ being 500. That maximum can be increased if 500 is ever reached.) Now use the functions to obtain the distribution of the maximum likelihood estimator:
m = 10; (* Sample size *)
n = 20; (* Number of items in population *)
(* Determine distribution of the maximum likelihood estimator given m and n *)
data = Transpose[{mle[#] & /@ IntegerPartitions[m, {1, n}],
prob[#] & /@ ss[m, n]}];
g = GatherBy[data, #[[1]] &];
dist = {#[[1, 1]], Total[#[[All, 2]]] // N} & /@ g;
TableForm[dist, TableHeadings -> {None, {"MLE", "Probability"}}]

The estimation problem you describe is related to capture/recapture statistical procedures and so likely this is a well-known topic (just not well-known to me). A Bayesian approach might be fruitful if you can characterize what you think about the possible values of $n$ as a probability distribution.