Use the curltester tool discussed above, and point them to it.

If they won't fix it, talk to the top dog at the hosting company and explain to them how unhappy you are with their service, yadda yadda yadda. If they want to keep your business, they'll do something about it.