Combinaciones de números aleatorios que no se repitan

[NSD]

Buenas tardes gente, tengo un problema que en un principio lo subestime como algo trivial pero al cual no le encuentro una solución aceptable.

Un cliente quiere hacer una especie de bingo electrónico, para lo cual, cada jugador tiene vinculados 15 números del 0 al 99 que debe generar el sistema de forma automática.

Las 3 reglas básicas son:

- No puede haber mas de 2 números repetidos en el mismo cartón.
- No puede haber cartones repetidos.
- El orden no importa.

Los puntos 1 y 3 no son difíciles, pero el punto 2 no se como resolverlo.
Pensé en tener 2 tablas en la base de datos:

-- Clientes --
Codigo Integer Autoincrement PK
Nombre CHAR
...

-- Cartones --
Codigo Integer Autoincrement PK
Cliente Integer FK(Clientes.Codigo)
Numero_1 Integer
Numero_2 Integer
Numero_3 Integer
Numero_4 Integer
Numero_5 Integer
Numero_6 Integer
Numero_7 Integer
Numero_8 Integer
Numero_9 Integer
Numero_10 Integer
Numero_11 Integer
Numero_12 Integer
Numero_13 Integer
Numero_14 Integer
Numero_15 Integer

Solución 1:
El algoritmo en php generaría 15 números al azar, los ordenaría y los guardaría en la tabla cartones.
Para saber si no esta esa combinación, esta acción estaría dentro de un while.
El problema de esto es claro: Cuando tenga mas de la mitad de las combinaciones insertadas, agregar un nuevo cartón al azar tardaría un montón y consumiría un montón de recursos y podría tardar mucho tiempo.

Solución 2:
Pre-Poblar la tabla cartones con todas las combinaciones posibles (Un montooooon) y luego seleccionar un cartón al azar de esa tabla que no este asignado para cada cliente nuevo.
Problema: La tabla Cartones es enorme, aun con pocos clientes.

¿Se les ocurre alguna otra solución posible?