It mostly has to do with the filesystem being used. The System V based extended filesystems (which most people know as "ext2" and "ext3") have the same history as the BSD filesystem ("ufs" or "ffs"), and neither is particularly efficient at handling a directory of more than 10k files or so. And it's not usually the lookup of a single file that's a problem; it's listing the directory (when doing index synchronization) that will be slow.
ext3 directories are hash databases, much faster than linear searches/listings.
not by default. it's a currently very-beta extension to ext3.
My understanding is that it's enabled by default for kernels 2.6 and up. I'm running 2.6.9-11.ELsmp, it's ext3, the directories are hash trees, and I did nothing special during the install.
To Dean's point about older stuff, true. There are probably a lot of 2.4 kernels out there.