Why is it true that every set can be classified as ordinary or extraordinary(not ordinary)? The statements of Russell's Paradox are presented below (in more or less elaborate form):


A set is called ordinary if it does not contain itself as an element.
A set is called extraordinary if it contains itself as an element.
Consider the set of all ordinary sets C.
C is either ordinary or extraordinary.
If C is ordinary then by definition of C (st.3) it should contain itself and therefore should be extraordinary. This contradicts the assumption and hence, C should be extraordinary.
But, if C is extraordinary, then it contains itself. This contradicts the very definition of C whereby it was to contain ordinary sets only. Therefore C cannot be extraordinary.


Thus, the paradox.

But.....

The problem is with the statement 4 above. It says C is either ordinary or not ordinary. This probably follows from the seemingly obvious statement:


  Every set is either of one type or not.


But, even though it seems obvious, what is the proof that it is true? In fact, there seems to be a counter-example, namely, *THE VERY SET: C. * 
As statements 5 and 6 together imply, it is impossible to classify C as either ordinary or not ordinary (i.e.,extraordinary).

Shouldn't a hypothesis (here, the statement in >blockquote&lt; ), however obvious or axiomatic it looks, be discarded as soon as a counter-example is found?
The reason people reject the definition of $C$ rather than the law of excluded middle (LEM- it has been mentioned in the comments) is because the latter seems way more intuitive: either somehting is true, or it is false; whereas the existence of $C$ relies on being able to define a "set of all objects that have property $\phi$", which is much less obvious.

However, a better reason to discard the existence of $C$ rather than the LEM, is the following: suppose for every property $\phi$, there is a set of all things that satisfy $\phi$.  Now let $P$ be any formula/property you like ($0=1$, "I am wonderwoman", "I can fly", really anything you like.). Consider $C = \{ x : x\in x \to P\}$. Then $C\in C \implies (C\in C \implies P)$ is true. However $(A\implies (A\implies B)) \implies (A\implies B)$ is an intuitionistic tautology, which means it doesn't rely on the LEM ! You can try to prove it by yourself and you'll see that nothing more than the definition of $\implies$ and modus ponens is necessary.

Therefore this implies $C\in C \implies P$, which by definition of $C$ implies $C\in C$, which together with $C\in C \implies P$, implies $P$.

Therefore $P$ is true, and I haven't used the LEM: accepting the existence of such $C$'s allows me to prove anything: that's why we discard it; so actually the paradox in question doesn't even need the LEM
This is a very odd presentation of Russell's Paradox. The introduction of the notions of "ordinary" and "extraordinary" sets actually leads to some confusion. Your statement 4 is simply not required as an explicit assumption to be discharged. 

Using a variant of FOL, you would usually prove by contradiction that $\neg \exists a: \forall b: [b\in a \iff b\notin b]$ as follows:


$\exists a: \forall b: [b\in a \iff b\notin b]\space \space$ (Premise)
$\forall b: [b\in C \iff b\notin b]\space \space$ (Existential Specification, 1)
$C\in C \iff C\notin C\space \space$ (Universal Specfication, 2)
$\neg \exists a: \forall b: [b\in a \iff b\notin b] \space \space$ (Conclusion, 1, 3)


By no means then is rejecting the Law of the Excluded Middle (LEM) required to resolve Russell's Paradox (RP).