Who is your hosting provider? Do you have a sample page I can view?
You can debug this by creating a page to dump the session after trying to send. Just create a new blank page that has just this on it:
<?php
@session_start();
var_dump($_SESSION);
?>
Then try to send the email from your form and visit this page. It might give more information with clues to what went wrong. If you can't figure it out, send me the URL so I can test the page and view the result and I can try to see if I can spot the problem.