this is a problem;m on the hosts end.
Even using a basic test email script that comes strait out of the network solution documentation, the email is not sending.
One thing i notice, in using phpinfo() to write the server settings, there is no value for the sendmail_path setting, that does not look to be correct.
most likely, the server updated its settings between when it was working and now that is causing the issue.