If mail() succeeds, the mail is going SOMEWHERE. It may of course not be being delivered.
I assume you have error_reporting(E_ALL) and there are no errors; moreover, you're checking that mail() returned true.
Therefore, the mail is somewhere, just not being delivered.
Your host should be able to help you- you must be able to get them to diagnose it and/or send you the relevant parts of the log file.
If the host is unwilling or unable to do this, they're obviously wholly incompetent, get a new one.
Mark