Look for available "spots" in a set

I'm looking for a way to programmatically look for an available (not used) spot in a list, usually a set of criteria. I could give you the example of a phone book: I'll generate phone numbers with specific rules (like, in this case, 7 digits, that's quite simple). The "generator" would choose an available number at random. This number won't be in the generator for the next try.

One possibility would be to store "used" phone numbers in a sorted list and look for the first available possibility. But that wouldn't be very random. The first generated number would be 000-0000, the second 000-0001 and so on. Another possibility would be to create the full list of all available phone numbers and remove these that are used already, but that would be a huge list. Assuming the generator is often used, performances would probably suffer.

Of course, I'm using the example of a phone number generator here, but that could be a different generator, for license plates or validation codes or whatever else, just defined by a set of rules. I'm trying to do that in Python, so examples in this language are welcome, but if you have articles to the theory in a different language, don't hesitate either, I'll just edit the question to include the answer if I can.

Thanks in advance,