I created a website that occasionally emails users when they register/change their password/etc.

Every other person however cannot or does not receive the emails. They are telling me that they are not even hitting their spam folders.

I don't know a ton about MX records or email sending, but when I "Edit DNS Zone" for this domain in particular there is 1 MX record listed there.

How do you go about troubleshooting botched PHP mail actions?

UPDATE: Here is my super-simple php mailing code:

$subject = "Subject Here";
$message = "Emails Message";
$to      = $verified_user_data["email_address"];
$headers = "From: [email protected]\r\n" .
"Reply-To: [email protected]\r\n" .
"X-Mailer: PHP/" . phpversion();

//returns true on success, false on failure
$email_result = mail($to, $subject, $message, $headers);

re: "are you saying that some do and some do not?" @ Jacob

Yes, basically. I send the emails containing the user's login username/password using similar code above. And I sell to fairly tech-savvy people. About 50% of the time, my customers claim they cannot find their welcome emails in their inbox OR in their spam box. It's as if it never arrived. I have the largest problem with Yahoo email addresses accepting my emails or so it seems.

re: "The MX record at your end doesn't factor in, although the SPF record (or lack of it) will. How much access and control do you have on the server itself?" @ John Gardeniers

I rent a dedicated server from Codero. Running CentOS 5, WHM + cPanel. I have full root access to the entire thing. Don't know much about MX records and/or SPF records. I just want the PHP mail function to work. It doesn't say much about that on the php mail function's help page.

re: "What are you using for the SMTP server?" @ JonLim

No idea. I use the code above when I need to fire off an email to a loyal customer, and that's it. Do I need to be worrying about SMTP servers?

re: "Could be many, many things. Can you describe how you're sending mail in your code? i.e. are you relaying off of another mail server somewhere, using the local sendmail or postfix? Any consistency in domains that can/cannot receive email? Do you have a PTR record setup from the IP address that you're sending mail out as? What about SPF records?" @ gravyface

I just described my simple code above!

I believe I have been having the most trouble with Yahoo domains, however "independent" domains (probably running spamassasin) ex. [email protected] as opposed to [email protected] seem to give a lot of trouble as well. I do not know if I have a PTR record setup from the IP address I'm sending my mail from. It's probably the same IP address that I setup my domain on, because I didn't do anything extra special. No idea about SPF records either, where can I go to create one?

Side Note: It's a crying shame what havoc the spammers have brought upon our beloved email system.