It is way too idiosyncratic and highly dependant on php.ini settings that often rely on a mail injector running locally and correctly configured. It needs to *Go Away* and I wish the PHP people would realize that.
PHPMailer is generally regarded as the best replacement, as it either completely avoids the local SMTP handling, or knows how to make it work correctly behind an API that makes sense.
But of course, you don't have the luxury of changing your code, do you? :-/ They probably turned off the local MTA. Unfortunately, that doesn't make mail() spit back an error because the local injector still runs! The way to debug that is to rummage in the local SMTP logs.
Wade.