As someone has previously pointed out, short word searches (such as Ur and Oz) are important. There shouldn't be a letter minimum, if at all possible. We should probably use google as a good guide for usability standards. Google lets you search for single letters, for example.
I understand there may be technical difficulties in reducing the minimum, but we should consider it a flaw if we have a four-letter minimum, or even a three-letter or two-letter minimum.
I've cc'ed wikipedia-l because this is a policy discussion as much as a technical discussion.
--tc