Potresti fare una tabella in cui memorizzi i messaggi (IDmsg, mittente, data, testo, e altri campi a seconda delle esigenze) e una in cui memorizzi le relazioni tra i messaggi e gli utenti a cui sono destinati (ID, IDmsg, IDutente).

Quando si invia un msg si creera' un record con il testo del messaggio, il mittente, la data e un ID univoco, e si creeranno tanti record quanti sono i destinatari nell'altra tabella, ognuno riferito all'IDmsg appena inserito (lo recuperi con mysql_insert_id()). Quando invece devi visualizzare i msg a seconda dell'utente, puoi gia' restringere di molto la ricerca tramite l'IDutente nella seconda tabella.

EDIT - dimenticavo: nel caso il messaggio inserito sia destinato a tutti gli utenti indistintamente, fai in modo di inserire un valore particolare (tipo -1) nella colonna dell'ID dell'utente cui e' destinato, per evitare di creare un record per ogni utente, e anche per fare in modo di includere in modo automatico gli utenti che vengono creati in seguito.