回答編集履歴

 

  いずれにしても不可解ではありますが、後者の場合なら.Item(key)で探査できるということは、まさか線形探査ではないと思いますので、連想配列はソートデータを持っているのだと思います。(もし線形探査なら、結果側のキーの並びによって処理時間が劇的に変わるでしょう。)

 

 

  とすると条件側に重複データが少ないと(つまり登録が多いと)ソートが何度も発生して遅いのかも知れません。