Goedel's theorem is not about nonexistance of foundation in mathematics, it's about existence of true but nonproveable statements in every nontrivial formal system.

One could imagine a hypothetical stronger result - maybe every nontrivial set of axioms can actually derive p^(not p)?

IANAM, but I do know it was an unassailable problem in Russell + White's efforts to found mathematics on a firm basis in Principia Mathematica [1].

[1]:http://en.wikipedia.org/wiki/Principia_mathematica#Consisten...

Provided the axiom set is recursively enumerable. The second order Peano axioms for the natural numbers are complete.