ok... yo te pregunto si el correo que te llega a tí te llega también con la dirección me@localhost o te llega como si te lo mandar el usuario desde su correo???
Mira un poco más sobre las cabeceras de mail() en el manual:
http://www.php.net/manual/es/function.mail.php
Saludos