'My mod_perl handler is started with use lib "/home/hive/25167/perl/lib" as described in the mod_perl manual on @INC.'

You have specified use lib in your handler, but the documentation says to put this pragma in your startup.pl. I think that may be your problem. Your @INC may be getting modified at runtime, not startup.

In the startup file directly alter the @INC. For example
  startup.pl
  ----------
  use lib qw(/home/httpd/perl /home/httpd/mymodules);
  1;
[download]

and load the startup file from the configuration file by:
  PerlRequire /path/to/startup.pl
[download]