I remember, before Wikipedia, there was a big debate on the original C2 Wiki about the usefulness of category pages. There is a fairly widespread opinion that categories are a waste of time, because no ontology can usefully classify the body of information that's out there. While it's natural to want to categorize things, people inevitably use very different systems of categorization (as seen by the dozen or so tags that many Wikipedia pages get), and so they'll never be useful to more than a small subset of people. See also Shirky - "Ontology is Overrated":
http://www.shirky.com/writings/ontology_overrated.html
At the time I left the C2 community, the debate was still raging, but there were still a number of vocal anti-category people. Evidently Wikipedia went the opposite way, but I'd argue that whether it's policy or not, categories are still useless. I always enter Wikipedia via Google; I browse around within it by hyperlinks. The value of Wikipedia is as a store of content, and not as a form of organization.
Category pages are useful as a supplement to good (not-deleted) primary pages.