Usually, this kind of issues lies on the server end.
Take a look at this post - Adobe Muse Contact Form - The server encountered an error - PHP - The SitePoint Forums
A somewhat same issue as yours, however, the hosting it has a different technology and settings.
Even your host might have some sort of settings which need to be unblocked.
Please check with them once again, also check if the email used in your form is compatible with them.
Let us know how it goes.
I think I've fixed the issue. It seemed to be related to the reCAPTCHA. When I changed this from the 2.0 version to the older version it started working. Seemingly there's something in the 2.0 version which isn't compatible.
Thanks for your help.
Has anything further been fixed re this issue? I also have the reCAPTCHA issue - only reCAPTURE 1 works but apparently Goole are removing it WEF March 2018...that means SPAM! I have seen a number of complaints of the same nature but neither Google or Muse have responded with a solution......