This is standard behavior (the placing of modules in the directory hierarchy like this). Note your perl -V gives you 4 items in @INC that correspond to equally nested directories with a prefix of /usr/lib/perl5. You're either going to have to recompile Perl to look in this place as well, use multiple 'use lib' statements like you're doing, or combine them all onto one 'use lib' statement:

use lib '/prefix/site_perl', 
        '/prefix/5.00503/', 
        '/prefix/site_perl/5.005/, ...;
[download]

The last alternative I'd recommend is to set the PERL5LIB environment variable to include these alternative directories. Set this like you'd set the PATH under unix: a colon-separated list of directories. If you're running under a web server like Apache, you'll have to tell Apache to set these first, or be sure they're set when Apache starts (in its startup script).