Beh in modo molto semplice e premettendo che l'invio sia uno a uno (nel senso che il messaggio non può essere spedito contemporaneamente a più utenti) io la tabella la costriurei con i seguenti campi:

- id messaggio
- id mittente
- id destinatario
- oggetto
- messaggio
- data invio
- flag che indica se il messaggio è già stato letto.

Che ne pensi?