ノグさん、こんばんは。

＞「待ちなし」とは、大量データの検索の場合、複数のクライアントから同時に検索を行っても
＞1個所の検索と同じ様に時間のロスが発生しないように結果が返ってくるイメージを言っています。
＞リモートオブジェクトではキューが生成され、順に処理するとアプリケーションテクニックに
＞記述されていたので、同時に実行されないと思っていました。

私の記憶が確かならば（死語？）、キューが作成されて順に処理されるのは、
共有オブジェクトの関数を呼んだ場合だけだったと思います。
普通にリモートオブジェクトの関数を呼ぶだけなら、ほぼ同時に結果が返ることは
実証済みです。（ネットワーク負荷やらDBMS側のオーバーヘッドなどを除く）

＞別々のスレッドが生成されるという事ですが、データストアも共有することは無いのでしょうか？

サーバAPの中で生成/実行するデータストアは、各スレッドごとに異なるインスタンスを持つはずです。
そもそもDBセッションからして別々になっているはずで、データストアの実体を共有化することは
できないと思います。

共有オブジェクトの持ち物としてデータストアを生成すれば別ですが、普通にリモートオブジェクトの
持ち物として生成してあれば、そのデータストアはセッション間で共有していないと断言できます。

やはり、検索そのものにパフォーマンス上の問題があるのではないでしょうか？
（または検索結果の行数が多いとか...）

どうしてもダメなら、要求と結果の受信を別々のタイミングで行なう「非同期処理」にトライしてみると
良いでしょう。
ちょっとめんどくさいですが、「サーバプッシュ」というテクニックを駆使すれば可能です。