Thanks for all the suggestions guys but I have managed to get the problem solved with the reluctant help from the hosting company. I think they received a lot of complaints so they sent an email to all their customers notifying them that people who use custom scripts will need to add a -f parameter for their scripts to work. As soon as I did that, normal service was resumed. Yippee!!
Here's the script now in case it helps anyone else (have removed the email address):
<?
$sender_address = $_POST['sender_address'];
$sender_email = $_POST['sender_email'];
$sender_phone = $_POST['sender_phone'];
$sender_message= $_POST['sender_message'];
$sender_name= $_POST['sender_name'];
$ToEmail = "freeola.hosted.email.adress";
$ToName = "Nick";
$ToSubject = "$sender_address";
$EmailBody = "$sender_name has sent you a message from your website \nEmail: $sender_email\nPhone Number: $sender_phone\nMessage: $sender_message";
$EmailFooter="\n";
mail($ToName." <".$ToEmail.">",$ToSubject, $EmailBody, "From: ".$sender_name." <".$sender_email.">", '-f freeola.hosted.email.adress);
Print "_root.pages.EmailStatus= Message sent successfully.";
?>