> 有り得ないなんて決め付けずに実験してみなさい｡
実験したもん。検索時間に関してだけど。（メモリ効率の測定方法がわからんない）
結果は、それぞれソート済みベクタが、
１．連想コンテナを上回る場面がある。
２．連想コンテナを下回る場合でも、その差は大きいとは言えない｡

んで、１については、要素数が多い場合が該当しやすいような気がする。
２については、「比較」の処理に比べて「次の比較対象へ移動」の処理が
無視できない場合に該当しやすいような気がする。

> ソート済み vector に対して
> set,multiset に対して
そのテスト、vectorの内容をset,multisetと等価にするために、
vectorに対してどんな操作がしてありますか？

わざとそこらへんをしくじった状態でテストしたら、
http://www.tietew.jp/cppll/archive/5687
↑と同様な結果が得られたのですが。
ちなみにテスト環境はcygwin gcc-3.2。

ってなわけで結論：
More Effective STL 第23項
「連想コンテナをソート済みベクタに置き換える事を検討しよう」
検索速度・メモリ効率に不満を感じた場合には、検討の余地が十分にある｡