You've followed directions carefully to troubleshoot this - that puts you head and shoulders above 97% of the people here! :-)
I think it may indeed be time to talk to your host. For instance, they may indeed have security settings that block some domains or IP addresses. I remember in the past when huge swaths of AOL email addresses were blocked by email servers because of the tremendous amounts of spam from those. If you have the email address the sender is trying to use, that will help more.
In the meantime, you could try doing a couple more tests from the live form, each time filling in different email addresses on the form itself, and see if those go through. If so, your site visitor may be being blocked.
You could also try using your form with no Captcha or Akismet and have the person try again, or do some of your own testing.
If none of that works, you could try another contact form. I have enjoyed using Contact Form 7 in the past. But Mike's form is great.
Hope that helps a little,