1
The first question is actually quaternary : Its answer could indeed be either "animal", "vegetal" or "mineral" but also "neither" as, if I want the others players to guess something which nature is either "lexical" or "boolean", or "numerical" (hence turning the game into a "Mystery Number" game), but also "historical", a "quote", "synthetic"...
This raises the total amount of possible answers to 2097152 which is 4 x 2^19 (2^21 would be shorter but a bit obfuscated).
Now, if we deal with common nouns, let's take the Oxford English dictionary which contains 231,100 entries in its 1989 Edition.
Of course, we may also want to guess some proper noun which enlarge this lexical set to a virtually unlimited cardinal.
Let's analyze which kind of binary (yes/no) question may be asked :
  1. Nature : Material / immaterial
  2. Nature : Living / Inanimate
  3. Nature : Natural / Artificial
Suppose one dichotomically got through Material / Living / Articial, we may then direct our following questions toward something related to genetic engineering (clone (Dolly ?), Monsanto's stuff...)

But now, if the answer to the first question had been "Immaterial", it might have been a good idea not to continue with the proposed 2nd question (Except if you want to make the players guess something which is related to something metaphysical, in which case, the obvious 2nd question would have been : "Is the answer related to metaphysics ?")...
That's why, Ariels, though I really liked your answer, I don't consider it correct as I consider the number of possible questions should rather be over 2^1 million (at least) hence, leading us to a number of 2^(1 million of millions) possibilities which is IMHO quite a lot before the game becomes boring.

UPDATE: I just visited the http://www.20q.net web site which URL was given in the Twenty Questions node.
Funny : for /dev/null it suggested me The Holy Spirit, then silence which was quite close in the latter case.