I wonder if the problem is that you’re sending that message using whatever the person filling the form in entered as their email address, as the ‘from’ address. This may be a security problem, in that I’d expect a hosting company to check that you’re sending emails from an address that you’re paying them to host, and not spamming and so on.
Try changing it so that the $from value is another of your own (or the site owners own) email addresses, and include the form-fillers email address in the body of the message.