Threshold to stop generating random unique things

Given a population size P, I must generate P random, but unique objects. An object is an unordered list of X unique unordered pairs.

I am currently just using a while loop with T attempts at generating a random ordering before giving up. Currently T = some constant.

So my question is at what point should I stop attempting to generate more unique objects i.e. the reasonable value of T.

For example:

1) If I have 3 unique objects and I need just one more, I can attempt up to e.g. 4 times

2) But if I have 999 unique objects and I need just one more, I do not want to make e.g. 1000 attempts

The problem I'm dealing with doesn't absolutely require every unique ordering. The user specifies the number actually, so I want to determine at what point to say that it is not reasonable to generate any more.

I hope that makes sense

If not, a more general case:

Choosing N numbers, at what value of T does it start to get very difficult to start generating more unique random numbers from the possible N.

I'm not sure if T would be the same in both cases but maybe this second case would be sufficient for my needs. I need a relatively large threshold for small values of N and a relatively small threshold for large values of N.

Not that it matters, but this is for a basic genetic algorithm.