Based on my experience, out of five or so categories (classic and people), the game was able to answer two out of five times before the twentieth question. The three tougher answers were answered with fewer than thirty questions.
The game FAQ tells us about the possibility of 'contradictions', explaining: "Since 20Q learns everything it knows from the people who play, it is dealing with opinions, not facts. It's more like a folk taxonomy. Folk taxonomies are generated from social knowledge and are used in everyday speech. Since the opinions of people often differ, 20Q must do its best to sort out conflicting information. Contradictions are also one of the main ways that 20Q learns more about something. If enough people contradict what it currently thinks, it slowly changes its mind about that subject and eventually the contradictions will no longer happen." Try 20Q!