Here's a relevant link:

http://en.wikipedia.org/wiki/Intuitionistic_logic

Incidentally (a further parallel to the Axiom of Choice) Intuitionist Logic is also referred to as Constructive Logic.

http://en.wikipedia.org/wiki/Constructivist_mathematics

One branch of constructivist mathematics eschews the axiom of choice, and all do not allow proof of existence by RAA on non-existence.