Maybe it's easier to debug this by just taking a look at what is actually going on under the hood — e.g. using strace.  Just create a wrapper something like this

#!/bin/sh
strace -o /tmp/strace.out -efile /path/to/your-cgi-script.pl
[download]

(The -efile is optional, and filters the output to only log file-related system calls, such as open, stat, access,...  In case your script involves subprocesses, you might want to use option -f, in order to trace forked processes, too.)

Then compare non-working vs. working, i.e. the output you get when running it via the webserver against the output you get when you call it on the command line.

This should give you a rather precise idea of which paths are being searched, what files are being opened, or aren't found, etc.  Maybe it's worth mentioning upfront that it's perfectly normal to get lots of "ENOENT (No such file or directory)" — this just shows what's being tried, not necessarily that there's a problem. It only indicates a problem if some file which needs to be loaded, is producing nothing but ENOENTs, or some other error. You get the idea...  In case you're having difficulties interpreting the details, just post the output here.