In some cases, if you fill in the From Display Name, the email will not be sent, try leaving that blank.
Have you set a redirect page for if look up passes and if look up fails? Which one are you redirected to?
check with the host to see if they can look into the SMTP server error logs to see why the email is not being relayed.