Are you sending the mail directly from PHP or are you sending to a mail relay you control (localhost)? I'd suspect your mail header are not correctly filled first. If you're not using a local relay your mail may be rejected?

Is there anything in any logs anywhere?