I agree that contacting your host provider is a good idea. I too was having trouble with my contact form, and then contacted GoDaddy (who is my host provider) and here is what the representative wrote to me about what solved the problem:
“it seems that the recipient e-mail inside of includes/form_1.php was set to a default firstname.lastname@example.org, after changing this to your e-mail, it seems to have started working!”
Ever since then my contact form has been working. To be honest I really don’t understand what happened, but hopefully that will help someone.