Do all classes of problems fall into the set {P,NP}?

No, consider the http://en.wikipedia.org/wiki/Halting_problem, which is undecidable.  All problems in NP (and P) can be solved in (at most) http://en.wikipedia.org/wiki/NP_(complexity)#Relationship_to_other_classes.  Turing proved that the halting problem can't be solved at all.* * with a Turing machine

You seem to be under the common incorrect impression that NP means "solvable in non-polynomial time". That is false. NP means "solvable in nondeterministic polynomial time". In other words, NP means "if I show you the solution, you can verify it in polynomial time". Before proceeding any further (and reading the other fine answers here), please make sure you understand the concept of nondeterminism.

No, P and NP do not encompass all classes of problems; they are near the bottom of the polynomial hierarchy, which is a list of related classes you can make as long as you desire. If you enjoy formalisms and details there is a readable treatment in "Introduction to the Theory of Complexity" (Bovet and Crescenzi, 1994), and you can find a summary on Wikipedia too. To try an informal description with less notation, more intuition, and perhaps a few inaccuracies: the hierarchy has two 'branches', one for existential questions ("is there an x such that A is true?") and one for universal ones ("is it so that for every x, A is true?"). NP questions are basically of the first kind, and its limit is visible already here: universal questions in one variable belong to 'co-NP', at the bottom of the other branch. You can make problems which combine these, e.g. "is there an x such that for every y there is a z for which A is true" uses 3 quantifiers (two existential and one universal), which puts it on the 3rd level of the hierarchy. This one would go on the existential side (for being answerable by an NP-oracle-which-asks-a-coNP-oracle-which-asks-an-NP oracle). As you can imagine, one can take any problem class like this and make it one step harder by slapping another "is there a <thing> such that", or "is it true for all <doohickey> that" in front of it. 2-player games make a nice example, the complexity of finding an optimal playing strategy goes something like ( is there a move such that ( for all moves my opponent can make ( there is a move such that ( for all moves my opponent can make ( there is a move... ))))), and goes on for as long as you care for. (Sidebar: if you don't care about time, this sort of question is certainly solvable in limited *space*, so the class of problems solvable in polynomial space (PSPACE) contains the entire hierarchy, AFAIK. It bears mention that I have silently taken the liberty of assuming that P != NP here. If P = NP, then the entire hierarchy (co-NP included) collapses to one big, happy family of problems solvable in polynomial time - but then, the question wouldn't make sense in the first place.

Check out this wonderful venn diagram from wikipedia: P is definitely not NP complemented. I think it's a common beginner mistake to think that N stands for 'not', but it actually stands for 'nondeterministic'. I won't go into that here, but what you should know: Anything in P is in NP. There are problems outside of NP, like uncomputable problems. There are also computable problems outside NP; I believe the NEXP-hard problems are the easiest problems we can prove to be outside NP. If P≠NP, then there are problems in NP that are outside of P (including NP-complete problems).

Hoo boy. Brace yourself, you're only seeing the tip of the iceberg...

No. There is a wiki site which lists all known classes of problems. I believe they have listed 450 so far. https://complexityzoo.uwaterloo.ca/Complexity_Zoo

The technical answer to the headline question is 'it isn't known'. There are a class of problems called PSPACE-Complete, which many computational theorists believe to be outside of NP. To handle the followup, even if it's shown that PSPACE-Complete problems fall into NP, that won't be the reason. NP is a superset of two classes - 'P' and 'NP-Complete. NP is absolutely NOT the complement of P.

No, P and NP are very very small part of set of all languages. And they are not complement. For example NP-complement has some problems especially NP-complete which is not yet proved to be in NP.