Io farei così:

All'apertura della sessione controllerei il numero di msg che hanno l'utente loggato come destinatario e lo segno in una variabile di sessione $Session[NumeroDiMsgInIngresso] , questa variabile di sessione ovviamente faccio in modo che venga aggiornata se l'utente in questione fa delle modifiche (per esempio cancella la posta), ogni TOT secondi lancio lo script AJAX (io ho sempre usato la setinterval()) che lancia una pagina php che interroga il database facendo un count e restituisce il valore :

RisultatoDelCount - $Session[NumeroDiMsgInIngresso]
e poi aggiorna
$Session[NumeroDiMsgInIngresso] =RisultatoDelCount
nella onreadystatechange farei tipo:

codice:
 
    xmlHttp.onreadystatechange=function(){
        if(xmlHttp.readyState==4){
            alert(xmlHttp.readyState);
            if(xmlHttp.status==200){
               if(xmlHttp.responseText !="0") //penso che lo zero poi venga interpreato come stringa
                 alert("Hai "+ xmlHttp.responseText +" nuovi messaggi.");
            }
        }
    }
Il problema è un pò diverso per i messaggi che ti arrivano quando non sei loggato, in questo caso dovresti mettere come attributo nella tabella messaggi un campo Read booleano e quindi semplicemente quando ti logghi fai il count degli elementi he hanno l'utente loggato come destinatario e il campo Read su falso (Questa soluzione è veloce ma poco pultia, l'utente potrebbe avere dei vecchi messaggi non letti), ovviamente in questo caso dovresti anche impostare correttamente il campo Read quando leggi il messaggio.. Per risolvere invece il problema dei vecchi messaggi non letti probabilmente invece c'è bisogno di gestire diversamente le sessioni magari con l'ausilio di un db ma diventa un pò più complicato...

Ovviamente sono solo idee eh nulla di sicuramente funzionante e giusto