This is a standard statistical problem. It goes under a number of names, which is probably why you haven't been able to find it by Googling. In ecology, it's called "estimating species richness", and in computer science it's called "stream estimates for $L_0$.". The classic solution is Good–Turing frequency estimation, which was developed during the second World War. It's still good enough for many practical purposes. I'd start by reading about that, and if that's not good enough for your application, following the literature forward from there.
This is a standard statistical problem. It goes under a number of names, which is probably why you haven't been able to find it by Googling. In ecology, it's called "estimating species richness", and in computer science it's called "stream estimates for $L_0$.". The classic solution is Good–Turing frequency estimation, which was developed during the second World War. It's still good enough for many practical purposes. I'd start by reading about that, and if that's not good enough for your application, following the literature forward from there.