Gah I wish I'd known this:

As soon as Perl encounters such a directory, it will stop searching/

Found a directory in INC that was readable but not executable; changed to 755 and we're past the issue.

Still have to figure out why that directory is in INC in the first place; it's not in there when I check INC from the shell, and I don't see it anywhere in the apache config.

But things are working now. Thanks to both of you!