secondo me si può fare in questo semplicissimo modo:

1)quando si manda un messaggio privato ad un'altro, si fa anche un'altra query ovvero:
UPDATE utenti SET posta = 'Nuova' WHERE Nick='$_POST[Nick]

2)l'utente che riceve il messaggio avrà una codizione nel profilo:
if($row[posta]==Nuova) { echo"Ci sono nuovi messaggi"; } else { echo"Non ci sono nuovi messaggi"; }

3)Nella pagina di visualizzazione del messaggio c'è la query:
UPDATE utenti SET posta = '' WHERE Nick='$user_id'// che riporta tutto alla normalità!