What I found after Googling is that there is a theorem by Sierpinski which shows that if we make an additional assumption about the cardinality of [R]^\omega, w

What I found after Googling is that there is a theorem by Sierpinski which shows that if we make an additional assumption about the cardinality of [R]^\omega, which seems to be approximately the same as the boolean prime ideal axiom, then there is a non-measurable set. Thus the existence of non-measurable sets is implied by principles weaker than full choice, but that's not too surprising. The case of measure theory is particularly interesting, though, since you don't even need to change your underlying logic to get a better model. For instance, if you base your "measure theory" on valuations on locales instead of measures on sigma algebras then the theory itself becomes simpler and the Banach-Tarski "paradox" goes away. Briefly, in locale theory, your "measure" is defined on sublocales instead of subsets. While there are more sublocales than subsets, the condition for when two sublocales are disjoint is stronger. This is what breaks the Banach-Tarski construction. The orbit subsets used in Banach-Tarski still exist, but while they are disjoint as sets, they are not disjoint as sublocales and thus don't decompose the volume of the sphere.