Oooh, a sudden change in the ability to execute external programs from within PHP? Sounds like someone's running on shared hosting, and their hosting provider suddenly decided to bump up the security on their servers (probably because they got massively pwned) and didn't bother to tell anyone (because "what could it break?"). In that case, you throw up your hands and move to a shared hosting provider that provides a professional service and doesn't go changing things for the hell of it.
In your case, though, that's probably a bit less likely, because you state you're on a "virtual dedicated server" (although the tortured terminology suggests marketroid interference, which is never a good sign). However, the fact that this has "suddenly stopped working" leads us inexorably to the same conclusion: something's changed, and whoever changed it didn't test things properly first.
So, what you do is review the change management history for the machine and identify what changed around the time that the problem occured. Or, since you don't have change management history (an assumption, but one I'm willing to put money on), you talk to everyone who has root on the box and ask them what they've done (if lots of people have root, then give up and build a new box with decent security and management policies).
You can also try and narrow down what's changed by looking in the package management logs (I think RHEL4 had logging of all package installs/upgrades, but I last touched RHEL4 two years ago, and I'm getting a bit fuzzy), command shell history, sudo logs (if you're real lucky), and doing strategic find -mtime -N runs to see what files are newer than whatever timeframe you've identified for service failure. Backups (assuming you keep archival backups, which you certainly should for configuration) can be helpful in identifying exactly what was changed.
Once you know what's changed, you examine the changes and try and narrow down what's gone wrong. Anything to do with PHP, your MTA, or your webserver are obvious immediate candidates, but don't go dismissing seemingly innocuous changes so quickly -- if you're not sure, keep it in the "possibles" list. Then you have the entertaining job of trying to reverse changes out until you find the problem. This is a pain-staking and laborious job, frought with peril, and if there's multiple changes that impact the problem, you'll likely be there a long time.
Sound difficult? Sure is. That's why you do the job properly to begin with (plan, test, document) and don't skimp on the details.
/usr/sbin/sendmailfrom a shell?