It seems like you have multiple layers of issues here, but your description of the app is not clear enough yet to lead to useful advice.

One layer: you developed on linux, and someone wants you to port to ms-windows?

Another layer: it's a web app that depends on Perl / CGI / CGI::Application, which is obviously available on your web server, and someone wants you to port it to other web servers where these things might not be available (yet)?

Yet another layer: the people who manage those other web servers might know nothing about (or are resistant to) using Perl?

If it were a stand-alone command-line app (as opposed to a web app), you could get over the linux/windows and perl-challenged recipients issues by using a windows box yourself to create an executable (*.exe) file from the perl script and pass that around. But I gather it's not this sort of app.

If the expected recipients are entrenched in asp.net and unwilling to accommodate Perl/CGI on their web servers, there's not much you can do about that -- they are basically saying "we don't want your app", and it's not your problem.