The problem is simple that the PHP-Mail function is not using a well configured SMTP Server.
Nowadays Email-Clients and Servers perform massive checks on the emails sending server, like Reverse-DNS-Lookups, Graylisting and whatevs. All this tests will fail with the php mail() function. If you are using a dynamic ip, its even worse.
Use the PHPMailer-Class and configure it to use smtp-auth along with a well configured, dedicated SMTP Server (either a local one, or a remote one) and your problems are gone.