One problem is that in the heat of programming, one does not often see how to generalize one's problem and then describe it in a way a CPAN search can find it.
Yup, this is precisely where perlmonks shines. Not only will people re-describe your problem for you, they will give you answers too.
So here's the problem as I see it: CPAN seems mostly useful if I know exactly what I'm looking for. Perlmonks is a great resource but people can take advantage of the monks. The perlmonk search sometimes rocks, but sometimes it's really frustrating, again if you don't know what you're looking for.
Starting from CPAN. The WAIT search is good to narrow down your search terms; it indexes module POD files and does OK on many-word searches. But WAIT is somewhat slow and the results are one-line links so you need to do some more digging in each result to find your search terms.
Starting from google. Doing a google search restricted to site:perldocs.com works as well, and perhaps better. perldocs.com indexes POD files and other perl documentation, and has two lines of context for each result, which is very useful. The higher-ranked results are usually close to what I was looking for.
Ultimately what I'd love to see is an integrated CPAN/perlmonks search, where search terms are weighted like google's, and results from perlmonks are also weighted by their reputation.