Sure, can you point me to a host that has no problems with anything whatsoever please...
I see your point, smartypants. The point _I_ was trying to make was that there are some baseline expectations for any host, and a response like, "We couldn't solve the problem with our own servers" would break the limit, in my opinion.

Happy to provide you with some good hosting options, if you really are interested. PM me for more info.

It is their eccomerce server, and yes Apache is running as CGI. Would this always cause this issue then?
Assuming the problem is at the CGI level, then I would say yes. Regardless, the problem is definitely at the server level, and it's up to your host to fix.