CGI Error... Being told its because of my permalink setup?

Hello,

Have had nothing but headaches with this hosting provider, but I have to stay with them for a few reasons which I won’t go into.

Anyways click the link below, then click any sub-page. You will get a CGI error. The hosting provider is telling me its because of the custom permalinks? I’ve done a couple dozen wordpress sites and always use this structure. The host is using a windows based server…

Any idea how I can remedy this? As I am sure a lot of you know this structure is the best for SEO reasons, and I really would like to keep this structure.

http://209.235.198.252/wp/index.php

I get

CGI Error
The specified CGI application misbehaved by not returning a complete set of HTTP headers.

so I looked at the headers

HTTP/1.1 502 Bad Gateway
Content-Length: 232
Content-Type: text/html
Server: Microsoft-IIS/6.0
X-Powered-By: ASP.NET
Date: Thu, 16 Aug 2012 02:57:36 GMT

I’ve only used WordPress on Apache servers that have .htaccess files to do the fancy URL stuff.

Did you set things up for IIS ??

This host does not give me access to IIS… I am really going to try and convince the client to move hosting over to my service… So frustrating!

From http://codex.wordpress.org/Hosting_WordPress

(Optional)(Required for MultiSite) Apache mod_rewrite module (for clean URIs known as Permalinks)

Maybe he’s willing to lose the “clean URIs”?