Using 1.5.6a

Having issues with email. First started a while ago, then did a restore and was working again. A week ago it started happening again, and a restore back a week or two will not fix it.

Not receiving emails from contact us page, and cannot send order emails from Orders section.
If I select PHP I get "ERROR: Failed sending email to: "my name" with subject: "Order Update #163" Could not instantiate mail function.
If I select sendmail I get "ERROR: Failed sending email to: "my name" with subject: "Order Update #163" Could not execute: /usr/sbin/sendmail -t -i
If I select SMTPauth (which has the proper fields filled out), it just hangs and I get a 500 internal server timeout white page.

My questions are, why would a restore fix it, why did a restore not fix it again, and why would I need to restore at all? What's going on?!