Premetto che non ho guardato a fondo il tuo script.
Comunque, se sei alle prime armi é meglio partire con il piede giusto.

1. Non capisco che bisogno ci sia di scomodoare le sessioni per passare l'esito di un controllo.

Non sarebbe più semplice passare l'esito in GET?

Codice PHP:
header ( "location: [url]http://miosito/contatti.php?error=1[/url]"); 
Ed in contatti.php recuperi la variabile error ed a dipendenza del valore stampi un messagio di errore.

2. $destinatario != NULL per verificare che il campo non sia vuoto non è proprio la forma migliore

Codice PHP:
if(!empty($destinatario)) //.... 
3. ereg("@" .... per verificare che un email sia valido é un po' pochino
3.1 ereg é deprecata da php5 e rimossa in PHP 6

Codice PHP:
preg_match ('/^([a-z0-9])(([-a-z0-9._])*([a-z0-9]))*\@([a-z0-9])(([a-z0-9-])*([a-z0-9]))+(\.([a-z0-9])([-a-z0-9_-])?([a-z0-9])+)+$/i', $_POST['email']); 
4. Che approccio é verificare se tutto è giusto, in quel caso inviare l'email e poi verificare se c'é qualcosa di sbagliato?

Verifica se c'è qualcosa di sbagliato, in quel caso interrompi l'esecuzione rinviando alla pagina contatti.php.
Se tutti i controlli sono stati superati, allora invia l'email