I agree with both John and Koen. Moodle docs needs a lot more content,...but it also needs better structuring.
Without constant restructuring and 'cleaning up', wikis tend to grow organically over time, like briar bushes of information, to the point where they become difficult to navigate. 89 first level categories in Moodledocs might seem a bit overwhelming to a first time user. And in practice, most people diving for doco are newbie users.
I suspect the reason that the search from the Moodle home page is better than the wiki search block is that it's powered by Google and uses their proprietary page-rank, whereas the search block in the wiki is more of a standard keyword search. Keyword search works best when the same keywords are widely used to mean the same things.
I don't think I'd agree with Koen's statement: "if the internet was structured, search engines would not be necessary." The main reason the Internet has become so dependent on search is that it has become so huge. The larger the information repository, the more search-driven its users become. Even if they knew how to drill down to something, if search is quicker, search wins.
Furthermore, even if the Internet had a beautifully logical structure, it would only be beautifully logical to the person that designed the structure. Let's face it. Everybody has a slightly different way of thinking and ordering things in their mind. Information architects will readily tell you that there are any number of ways to structure information and the one you go with depends very much on your specific target audience. The more diversified the audience, the harder it becomes to find a structure that fits. It becomes a compromise instead.
Since Moodle's audience covers a lot of different people from different disciplines, there will never be one single information structure that would seem intuitive to everybody. It will work for some and baffle others.
So the trick is to make the documentation more search-friendly while still giving people that are not so search-driven a variety of logical structures to choose from.