Te podrían dar algún ejemplo más concreto.
En principio se supone que tu servidor usa o está configurado como "PHPsuexec" .. esto implica que PHP se ejecuta como un CGI en el aspecto de que usuario usa para "aparecer" cara al Sistema Operativo .. normalmente "nobody".
La validación que hace el servidor de correo es de "quien" envia el correo .. si el "FROM" no se usa un usuario válido de ese servidor de correo (o por otro lado lo chequea), son rechazados. Si el "FROM" (que indicas en las $cabeceras) no es correcto o no lo indicas .. apareceras como "nobody" (usuario no valido o creado en ese servidor de correo lo más probable).
Intenta definir una cabecer FROM en tu e-mail que indique una dirección de e-mail válida en ese servidor (una tuya de tu dominio) .. pruebalo.
Sino, tendrás que "cambiarte" de usuario para ejecutar la función mail() .. para eso emplearías "sudo"
En otros sitios se habla de configurar tu servidor de correo (por cierto . cual usan: Exim? .. otro?) si es que tienes acceso a su configuración (desde un panel de control de tu servicio de hosting):
http://vpstalk.net/showpost.php?p=7202&postcount=15
Otra cosa que puedes hacer es usar:
PHPMailer
http://phpmailer.sourceforge.net
Enviar el e-mail por SMTP directo por tu própio servidor SMTP o el mismo de tu proveedor si es que lo permite usando cierta cuenta de correo (tuya) y autentificandote (esa classe permite autentificación).
De echo este método como veras es una amplia mejora al comando "mail()" de PHP .. y suele solventar los problemas de envio de e-mails pues la conexión se hace directa por "sockets" .. Es decir, se usa autentificación .. tal cual lo enviases con un cliente de correo cualquiera (Outlook .. etc ..).
Un saludo,