we did not have access to the error logs, I dove into the source to find the problem.

Next time, try some CGI::Carp solution, or try the script on another machine.

Well, the code was a mess. No strict, no warnings, no CGI module. They had hand rolled their own parser for postdata parameters. I modified it to the point where it uses the CGI module, warnings, taint mode, and strict.

Unfortunately, this is an unwritten CGI script coding standard. However, it is not always a problem. If it works and is maintainable and secure, it does not really matter much.
Messy code can be maintainable if it's documented well and set-up logically. Tools like perltidy can fix awkward indentation, so if that is the only problem, give it a try.
Code that doesn't use strict is not wrong per definition. Without strict, you're not forced to code without lexicals and without strict, no-one forces you to use symbolic references all over the place. Given that all code that does run with use strict also runs without, you should understand that code without it isn't always bad.
Warnings aren't errors because they are not fatal. They warn the programmer, but have nearly no meaning for the user. Of course, like strict, it's better to ensure that the code doesn't emit warnings and keep -w or use warnings in there, but it's quite common to remove it once code goes into production. Warnings are not important when the development cycle is over, and one can do without. (He who does will have more trouble finding bugs, but warnings are not necessary to create a good application.)
The CGI module is not a good module in my opinion. You complain about the code not using strict, but I think you missed that CGI.pm doesn't use strict either. Furthermore, CGI.pm is bloated, slow and parses in a way that does not please me. It is, however, very compatible with a lot of things.
Having your own parser can be a good thing, for example if you need to know the difference between query string and POST data. CGI.pm does not handle this the way it should: posted forms can have a query string too, and in many cases it's bad to mix the two.

I would consider rewriting the script from scratch in the spirit of Not Matt's Scripts, but I'm afraid that I am already too familiar with the code to create a legitimate independant implementation. Any advice?

Just Do It, but do so blindly, without looking at the original code. There is probably nothing specific to the algorithm.

Please note that I am not against strict or warnings, or think code that uses CGI.pm is bad. I'm just noting that bad coding styles don't always lead to bad code.

- Yes, I reinvent wheels.
- Spam: Visit eurotraQ.