Yaron -- I'm afraid you're a bit late since we're already done adding key lookup to the ArrayList.
Moreover, I don't quite see your point. Templates with fast key lookup and unique keys are already available in the collection package, namely Hashtable and SortedList. The latter provides access by key as well as by index.
The ArrayList key lookup was deliberately designed to have no impact on its existing functionality and performance. We don't need the extra data structures for a hashing algorithm, and we can insert multiple items with identical keys.
Lastly, while I don't know your situation I found that most of the collections I'm using have maybe 5-20 elements, and in that range an unsorted collection with linear searching is absolutely sufficient. Fast searching for large N comes with a huge overhead at small N (Hashtable) or when inserting elements (SortedList).
Just get a .NET decompiler like Reflector and look at Microsoft's hashtable implementation -- you'll be surprised how much auxiliary data it needs, and how many instructions have to be executed before
anything is found.