What is the minimum number of key-value pairs for which it makes sense to use a HashMap, as opposed to using a pair of arrays (one for keys, the other for values) with brute-force key searches?
Well, is there really that much of a performance loss using a HashMap? There is no synchronization penalty (unless you impose your own). You can tune the sizing by adjusting the initial size and load factor. Plus, do you really want to be responsible for "rolling your own" code to handle the dynamic resizing of the key and value arrays, inserting/removing data from these arrays, optimizing the searching algorithm, etc. Yuck!
In general, the performance hit associated with using a general purpose Map (such as the HashMap) is far outweighed by the benefits of using a simple interface backed by a tested algorithm.
The only reason I could see wanting to use arrays is to guaruntee the type of your key/values to add type checking and avoid casting. Still, if this is a critical aspect of your application, you can wrap your HashMap in another object to provide type-safety, and the casting overhead should be minimal.
Another alternative to creating a custom solution is to explore other collection classes, such as ObjectSpaces's JGL Libraries. There may be something there that would suit your needs.
So, to answer your question, I would say that the fewer the key-value pairs you have, the more reason you have to use a HashMap. Since the fewer the keys, the faster the search, why not use it for 2-5 key-value pairs. I would think that only when you get to many pairs (tens of thousands) and there is a performance problem you should consider an alternative. Basically, exhaust your search of tried-and-true collections before you try a custom solution. Let other people create these collections so you can focus on your application.
[Editor note: HashMaps of 10K pairs will function fine, assuming a good hashing algorithm for hashCode() [with evenly spread out keys]. Keep using it at 10K and beyond with no problems.]