Why can't we just claim a paradox invalid, just as the way we treat contradiction in mathematical proof? (i.e. if we arrive at the proposition inconsistent with the assumption, then we can immediately claim the logical impossibility of the assumption).
Paradoxes are indeed invalid arguments, but what makes them special is that they rest on seemingly unproblematic assumptions. We know, for example, that Achilles will in fact outrun the tortoise (Zeno's Paradoxes), we know that the surprise exam will take place (Surprise Exam Paradox), and so on. Because we know the conclusions of those paradoxes are false, we know that something is wrong with the arguments. The task then is to identify the assumptions that lead to the false conclusion.
Paradoxes can be called 'invalid' and ignored, but if taken seriously they can help us diagnose and fix problems with existing logico-mathematical frameworks. Axiomatic set theory and type theory owe much to Russell's Paradox, for example. The above mentioned Surprise Exam Paradox has led to lots of interesting developments in epistemic, dynamic, and public announcement logics. There are, of course, the classical ones, like the Sorites, the Liar, and so on. Each has opened some interesting door.
I claimed that paradoxes are invalid arguments. Sequitur's contribution inspired me to add that someone might ask: "invalid according to which logic?" I'd say classical bivalent first-order, but there are possibilities for significant 'paradox-preserving' deviations from that. What's important here is to realize that: you can't simply change the logic and claim that the paradox is resolved. Suppose classical logic C gives rise to paradox Π, but intuitionistic logic I does not. You cannot simply dispose of classical logic, adopt an intuitionistic one, and claim that you have handled the paradox. Even after doing that, fact will remain that Π is a paradox for C!, so one needs, if interested, to address why C enables the paradox.
Take paradoxes seriously, because they indicate that (at least) some thing is not as true as it seems.
Just to adress your question directly: We could treat paradoxes in the way suggested by you if the English predicates of truth and falsity were necessarily exclusive; that is if contradictions could not be true.
But whether this is so is a highly controversial issue. Proponents of weak paraconsistency say no, because (i) the English consequence relation is not explosive, i.e. contradictions do not entail everything (think of inconsistent fictions or theories, where apparently not everything holds) and (ii) consequence is truth preservation in all models (of a suitable non-classical logic) and (iii) models represent possibilities.
More boldly, propopnents of strong paraconsistency (aka dialetheism) hold that there actually are true contradictions and so true falsities are possible. Indeed dialetheists say that some paradoxes (such as the liar) are sound arguments. Non-trivial strong paraconsistency entails weak paraconsistency, but not the other way round.
If any of these positions can succeed depends on many intricate issues such as how best to treat paradoxes of self-reference (a strong justification for strong paraconsistency) and a quick settlement of the debate is not to be expected. So you're not justified in treating paradoxes by denying their validity.
A contradiction is something that cannot be true, because it refutes its premises.
In the strictest sense, a paradox is something that can be neither be true nor false, because refuting the premises provides an equally false set of premises.
Consider Russel's paradox: Does the collection of all collections that do not contain themselves contain itself? The question cannot be answered 'yes' or 'no'. Either answer implies the opposite. If it contains itself, then it does not meet the criteria for being admitted to itself. If it does not contain itself, then it does meet the criteria and must be included.
If you decide 'Russell's paradox is invalid.', what does that mean? It can only mean that the answer to that question has some truth value like 'Irrelevant' which is different from both True and False. This requires discarding the Law of the Excluded Middle -- because this falls flat into the 'middle' it is meant to 'exclude'.
This indicates that the basic naive intuitions involved in the statement are flawed. These can be worked around technically, but cannot really be resolved. Humans will still continue having the same flawed intuitions of logic and the paradox will continue to make a compelling case for the difficulty of reasoning correctly.
You can make up whatever special set of rules you want, but they will never be as compelling as naive logic, even though naive logic leads into plenty of paradoxes.
To my understanding a paradox is a logical argument that fails because it is built on inconsistent axioms, e.g. a tower built on clay. In contrast, a fallacy is a logical argument that fails because of a faulty argumentation, e.g. a tower built without a plumb-line. A contradiction show that the axioms and the conclusion cannot be true simultaneously.