The most interesting/relevant thing i found was in the Newman-Shepp's generalization of the coupon collector problem, which seems to be the exact dual problem of the balls in the emptiest bin ( = "how many balls do you have to throw to ensure there are $x$ in every bin [and thus in the emptiest] ")

According to http://en.wikipedia.org/wiki/Coupon_collector%27s_problem#Extensions_and_generalizations

...the expected number is $ p = n\log n + (x-1)n\log\log n + O(n)$

So my guess for the emptiest bin would be to invert this formula (express $x$ in function of the rest) , and i have a bound on the number in k emptiest, quite good if $ k << n$ (well, the estimation being for $n \to \infty$, this seems okay :-) )

Maybe i should see the proofs of this to see if there are ideas that can be adapted & formalized.