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

[noslenwerd]

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

[Mittineague]

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 ??

[noslenwerd]

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!

[Mittineague]

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"?