That sounds like one of two things:
1) A misconfiguration with the ASP hosting. Custom CGI scripts should run as custom ASP scripts (which are basically the same thing, but in a different language) would. This is all true unless 2) applies.
2) Custom CGI/COM/other objects and programs (not the scripts themselves, but actual objects and programs) need to be installed. Most hosts tend to charge a premium for this type of thing, if they offer it at all.
I don't know much about CGI or how it works (since I've never used it), but from my understanding of it, you're just scripting for the most part with it. And there are Windows plans out there that do support CGI and allow multiple accounts.
Sectorlink's Enhanced hosting plans do this. I have my dedicated server with them (since I have over 50 domains and install custom stuff a lot of the time, it just made the most economic sense), and I've been with them over 3 years. They're stable, reliable, and everyone I've referred to them have had no problems as well. It'll be cheaper for you to go this route than go dedicated.