In our case, CGI runs under the apache user, but the file owner is different, so by that statement I'd expect we'd run with taint mode by dafault.

This is a misunderstanding. File ownership has nothing to do with that situation. This mandatory activation of taint mode happens as a consequence of a setuid (or setgid operation: Changing the user id of a process.

So an error like this is about as useful as telling the coastguard "there is a ship in some sort of distress, SOMEWHERE in the ocean!"..

It more precise than that. require is the first step of a use operation, and it is the most likely culprit. I guess that somewhere in your effective @INC path you have a directory which is considered insecure by taint checks. This can be as simple as a relative directory, because in most cases the return value of cwd (i.e. determining the current working directory) is tainted.