As perrin mentioned here, the CPAN search is totalling smoking fast right now. That's a big improvement alright.
Oddly enough I was looking for Term::ReadLine::Perl this morning, and CPAN Search failed miserably. On the 3 pages returned it isn't there at all
Although this could be a failing of the index rather than the search.