Cita: Creo que la segunda forma es mejor, pero se me va a llenar la tabla de registros (no penseis que exajero con 3000, pueden ser muchos mas)
Así fuesen 3.000 millones, lo correcto es que cada usuario va en un registro. En todo caso lo que te está faltando es la tabla que relacione a los mensajes con los usuarios, siendo que manejarás mensajes destinados a multiples usuarios.
PD: Un registro con dos campos relacionales requeriría, para un mensaje enviado a 3000.000.000 usuarios, apenas 2.4 Mb en disco, mientras que poner los 3.000.000.000 de IDs en un sólo campo alrededor de 3 Gb...
Elige.