One other thought: as the number of tracked cards increases, the ln2 approximation becomes less accurate, as the median approaches the mean.

Consider the degenerate case: what's the median number of cards dealt from a single deck by the time you see all 52 cards? Certainly, the median=mean=52, and ln2 x 52 is a horrible estimate. I think the estimate works best when you're looking for a single result (e.g. a single ace of clubs, a single 28 in roulette, a single 3 on a die, etc.).

So I'm still leaning towards the median solution for this problem, but with an accurate calculation of it.