En la función mail() hay un 5° parámetro para definir el "FROM" si usas sendmail como MTA (no sé si será tu caso).
Por otro lado, la dirección de correo del "FROM:" debe ser real .. respetando la sintax del protocolo del e-mail y lo más seguro que si no indicas ahí una dirección de ese servidor, el mismo la cambie por una genérica del servidor en cuestión para evitar que se haga "SPAM" a nombre de otras direcciones "falsas".
Revisa la documentación de mail() al respecto:
http://www.php.net/manual/en/function.mail.php
Un saludo,