The devil is in the details of how you try to modify @INC.

push(@INC, "/my/directory");
use MyModule;
[download]

will not work.

use lib "/my/directory";
use MyModule;
[download]

should work.

use and BEGIN are evaluated "at compile time", before any other code is executed. So, in the first example use MyModule; is evaluated before @INC has been modified. The second example works because both statements are evaluated at compile time.

The PERL5LIB environment variable is, as was suggested, also useful. It, too, is processed at compile time.