fai così:

Codice PHP:
mail('mail@mail.com','oggetto','messaggio',$headers,'-fMAILVERA@TUOSITO.IT'); 
Devi aggiungere un parametro alla fine che è "-f" e (tutto attaccato) una mail REALE del tuo sito.

Avevo lo stesso identico problema... prova così, sono sicuro che funzierà