Could it be that E-Mails are being sent fine, but are caught by a spam filter? If this could be, allow me to cross-post myself:
A few bullet points (Assuming that mail() returns true and there are no errors in the error log) :
- Does the sender address ("From") belong to a domain on your server? If not, make it so.
- Is your server on a blacklist (e.g. check IP on spamhaus.org)? This is a remote possibility with shared hosting.
- Are mails filtered by a spam filter? Open an account with a freemailer that has a spam folder and find out. Also, try sending mail to an address without a spam filter.
- Do you possibly need the fifth parameter "-f" of mail() to add a sender address? (See mail() command in the PHP manual)
- If you have access to log files, check those, of course, as suggested above.
- Do you check the "from:" address for possible bounce mails ("Returned to sender")? You can also set up a separate "errors-to" address.
For german speakers, I have written a quite exhaustive "what to do" on this issue some time ago. See here.