Your numbers are correct. In fact, the old libraries of genomic DNA were
only 2000 to 5000 clones in total in each pool. And indeed these provided
adequate coverage of the genome to clone most any given gene in a few
thousand transformants. One of my favorite papers along these lines
proudly reports cloning the gene as one of 1300 transformants with YEp24.
The benefit of bigger (newer) libraries lies in better coverage of "toxic"
sequences (which is offset by the problems caused by high copy number
origins) and multiple overlapping clones of each gene. Then there is a
payoff to collecting a larger number of transformants.
In sum, if you are in the dark ages and still using the old YCp50 or YEp24
libraries, for example, don't worry. If you don't see it a few times in
the first 10-20 thousand transformants, it ain't likely to be in the next
100 thousand. Instead, I would go get one of the newer libraries.