You are having Godel-disease, which every mathematician goes through, until actually studying logic. The fact is, that Godel's argument is based on the notion of computation, which is absolute. You can define mathematics as follows:

* Matheamtics is the study of the problem of figuring out which computer programs halt and which ones don't.

The thing about computer programs, is that if they halt, you can see it, and if they don't, you can sometimes prove it. These things are absolute, and refer only to integers. To see that this definition includes nearly all of ordinary mathematics, consider any conjecture C, and ask

* Do the axioms of ZF (or ZF+large cardinals) imply C?

This question is about the halting of a computer program, it is asking:

* Consider the computer program DEDUCE, which starts with the axioms of ZF and applies logic, and if it finds statement C halts. Does DEDUCE halt?

If you can solve the halting problem, you know which theorems are consequences of ZF.

But this is not quite all of matheamtics, as you can see by taking statement "C" to be "program R doesn't halt", where R is the code of the program DEDUCE itself. This construction proves Godel's theorem.

Godel's theorem is not a limitation on mathematics, and Chaitin's intepretation is likely completely false. If you add the axiom that the program above doesn't halt (this is equivalent to the consistency of the axioms of ZF), then you get a stronger system. Iterating Godel's construction over all countable computable ordinals (the kind you can manipulate on a computer), for all we know, _proves every theorem of the form "Program P does not halt" (and even with oracles, so that it produces the answer to all matheamtical questions).

The iteration process makes the axiom system more complex, and allows even Chaitin's questions to be answered (demonstrably slowly, only as the ordinal becomes complex enough to have computational complexity greater than the complexity of the program you want to prove is minimal length). This makes mathematics incomplete at the upper end--- you need to give ever more precise descriptions of large countable ordinals.

This point of view places computations at the foundations, since unlike any other foundational concept, the concept of computation is independent of the axioms--- it is Turing computation in all reasonable definitions. Expressing all mathematical questions computationally makes it clear when they are testable, and the computational representations of models of set theory make it obvious that Banach Tarsky is just as false as true, since it can be forced either way.

The best way to rid yourself of Godel disease is as follows:

* Ordinal analysis: This is Hilbert's program under a new name. It is alive and well in Germany. It is groping toward proving the consistency of ZF from a large countable ordinal. A highlights of this is Kripke-Platek set theory, which, unlike ZF, has an ordinal complexity which is entirely understood.
* Cohen forcing: This is the analysis of models of set theory, but allowing one to adjoin new elements to the model which occur in any set where you have an infinite number of binary choices to select an element (like the set of reals, which have an infinite number of binary digits). Forcing makes it obvious that Banach Tarsky might as well be false (ZFC is not accurate in modeling the intuitive reals), you can take every subset of R measurable, you can make the continuum hypothesis true or false, and generally, you get absolutely undecidable questions about all collections that are too big to enumerate on a computer.
* Reverse mathematics: This tries to identify the exact axiomatic strength of each theorem in mathematics

Each of these are reasonably active things in logic, but they are not advertized because logicians try to keep things to themselves with obscure jargon and high barriers to entry. You can find a good introduction to Logic esp. forcing, in Manin's book. There are good English articles online (by the German school) on ordinal analysis, and Harvey Friedman is the founder of the program of reverse mathematics.

If you start by learning the completeness theorem, this is the first step to getting rid of Godel disease, which is just a sickness of the mind.