ちょっとずれてるので横からコメント

unshift、push で変更を加えた @INC(モジュール検索PATH)が使用されない
起こってる現象とこの認識はちょっと違う。

具体的に何が起こっているか説明する前に、Perlにはコンパイル(BEGIN) フェーズとランタイムフェーズという、2回コードが実行されるタイミングがある(まぁ厳密にはもう少し色々フックすることが可能だけど、とりあえず一般的にはその二つで大丈夫)。

これがどういうことかというと、順番にコードを書いているつもりでもコンパイルフェーズで評価される部分とランタイムフェーズで評価される部分があるということ。わかりやすい例としてはこんな感じか:

#!/usr/bin/perl
use strict;
print "Runtime!\n";

BEGIN {
    print "Compile time!\n";
}

BEGINで囲まれた部分はコンパイルフェーズで実行され、BEGINの前にあるprint文より前に実行されるはず。

で、一般的にモジュールを読み込む"use"宣言はどうかというと、これはコンパイルフェーズで実行される。"use"宣言というのは実は以下の構文と同等なのだ:
# use MyClass;
BEGIN {
    require MyClass;
    MyClass->import;
}

つまり、use宣言で扱うクラス名が発見されるためには、コンパイルフェーズ時に@INCが変更されてなくてはならない。mod_perlだろうとなんだろうとこれは一緒なので、mod_perlじゃなくても以下のコードではMyClassは見つからない:
unshift @INC, "/path/to/MyClass";
use MyClass;
つまり、"/path/to/MyClass"をuse宣言に認識させるためには以下のようにする必要がある:
BEGIN {
    unshift @INC, "/path/to/MyClass";
}
use MyClass;
これなら、どちらもコンパイルフェーズで動き、あとは読み込まれた順番に処理されるから問題無し!

まぁでもmod_perlを使うのなら、なにか制限がない限りstartup.plで@INCを普通にunshift/pushで変更しておくのが一番いいと思う。