Io farei così:

TABELLA utente

id_utente
....
altre info
....



TABELLA messaggi

id_messaggio
id_utente /*id dell'utente a cui è stato spedito il mex*/
....
altre info
....