Scommettiamo che così funziona?

mail($email,$titolo,$soggetto,$headers,'-fMAIL@MAIL.COM');

in pratica come ultimo parametro devi inserire "-f" e (attaccato) una mail REALE del dominio. In questo modo funge da verifica e se non arriva ti torna indietro a quella mail.

Io risolvo sempre così, ne parlo anche qua: http://script-php-js-mysql.blogspot....-arrivano.html