A.Tさん、こんにちは。

＞OUT引数の数は同じで、ストアドのSELECT文をなくして実行すると一瞬で終わります。

ということは、完全にストアド側の問題だと思います。
ストアド内のSELECT文が重たいのではないでしょうか？
※ 引数の構成が変わっていないのなら、PB?ORACLEインターフェイス間の負荷のは同じはずですよね。

「SQL*Plusで実行した時は一瞬で終わる」との発言がありましたが、以下のようにやっていますか？
SQL> VAR in01 VARCHAR2(10)
SQL> VAR out01 NUMBER
SQL> VAR out02 NUMBER
SQL> EXECUTE :in01 := \'TEST\';
SQL> EXECUTE proc_name( :in01, :out01, :out02 );
SQL> PRINT :out01
SQL> PRINT :out02

この要領でやっても「一瞬で終わる」のなら、ちょっと原因がわかりません。

＞・PB6.5に対し、Oracle8.05を使用しています。（SQLCA.DBMSには、O84 ORACLE 8.04で設定しています）これに問
題がありますか。Oracle8.05がサポートされてないとか。

アシストさんのＨＰの情報では、\"O84\" のインターフェイスは Oracle8.04と 8.05をサポートしているようです。
※ サポートしているといっても、100%問題がないかどうかはわかりません。