bisogna farlo contare da SQL. Intanto per capirsi bisogna che ragioniamo su valori identici. Per te mi pare esiste = 0 significa che esiste. non e' molto logico. Premesso che forse hai una tabella di utenti (o no?) come fai ad avere $id_utente?

Detto questo mi riferisco (per mia comodita') ai supposti valori di "esiste" espressi prima.

Puoi fare la conta con una UNION e poi sommi semplicemente i risultati ottenuti. es:

Codice PHP:
$count = mysql_query("SELECT 1, COUNT(*) 
                      FROM messaggio_privato 
                      WHERE esiste IN(1,3) 
                      AND id_utente_ric=$id_utente
                      UNION
                      SELECT 2, COUNT(*) 
                      FROM messaggio_privato 
                      WHERE esiste IN(1,2) 
                      AND id_utente_sender=$id_utente
                      ";
while($row = mysql_fetch_row($count)) {
   $num[] = $row[1];
}

$tot_records = array_sum($num); 
in questo modo puoi anche sapere quanti sono i campi sia da rx che da tx. Nota che ho messo 1 e 2 prima di count(*), bene, ci vogliono perche' nel caso di risultato uguale la UNION sovrascriverebbe il record e te ne renderebbe solo 1 nel result set.

ma prima di tutto bisognerebbe normalizzare il campo "esiste" ... assegna quello che ti pare ma necessita che la logica utilizzata sia comprensibile ad entrambi.