Are proofs by contradiction really logical?

Proof by contradiction, as you stated, is the rule$\def\imp{\Rightarrow}$ "$\neg A \imp \bot \vdash A$" for any statement $A$, which in English is "If you can derive the statement that $\neg A$ implies a contradiction, then you can derive $A$". As pointed out by others, this is not a valid rule in intuitionistic logic. But I shall now show you why you probably have no choice but to agree with the rule (under certain mild conditions).

You see, given any statement $A$, the law of excluded middle says that "$A \lor \neg A$" is true, which in English is "Either $A$ or $\neg A$". Now is there any reason for this law to hold? If you desire that everything you can derive comes with direct evidence of some sort (such as various constructive logics), then it might not hold, because sometimes we have neither evidence for nor against a statement. However, if you believe that the statements you can make have meaning in the real world, then the law obviously holds because the real world either satisfies a statement or its negation, regardless of whether you can figure out which one.

The same reasoning also shows that a contradiction can never be true, because the real world never satisfies both a statement and its negation at the same time, simply by the meaning of negation. This gives the principle of explosion, which I will come to later.

Now given the law of excluded middle consider the following reasoning. If from $\neg A$ I can derive a contradiction, then $\neg A$ must be impossible, since my other rules are truth-preserving (starting from true statements they derive only true statements). Here we have used the property that a contradiction can never be true. Since $\neg A$ is impossible, and by law of excluded middle we know that either $A$ or $\neg A$ must be true, we have no other choice but to conclude that $A$ must be true.

This explains why proof by contradiction is valid, as long as you accept that for every statement $A$, exactly one of "$A$" and "$\neg A$" is true. The fact that we use logic to reason about the world we live in is precisely why almost all logicians accept classical logic. This is why I said "mild conditions" in my first paragraph.

Back to the principle of explosion, which is the rule "$\bot \vdash A$" for any statement $A$. At first glance, this may seem even more unintuitive than the proof by contradiction rule. But on the contrary, people use it without even realizing. For example, if you do not believe that I can levitate, you might say "If you can levitate, I will eat my hat!" Why? Because you know that if the condition is false, then whether the conclusion is true or false is completely irrelevant. They are implicitly assuming the rule that "$\bot \imp A$" is always true, which is equivalent to the principle of explosion.

We can hence show by a formal deduction that the law of excluded middle and the principle of explosion together give the ability to do proofs by contradiction:

[Suppose from "$\neg A$" you can derive "Contradiction".]

  $A \lor \neg A$. [law of excluded middle]

  If $A$:

    $A$.

  If $\neg A$:

    Contradiction.

    Thus $A$. [principle of explosion]

  Therefore $A$. [disjunction elimination]

Another possible way to obtain the proof by contradiction rule is if you accept double negation elimination, that is "$\neg \neg A \vdash A$" for any statement $A$. This can be justified by exactly the same reasoning as before, because if "$A$" is true then "$\neg A$" is false and hence "$\neg \neg A$" is true, and similarly if "$A$" is false so is "$\neg \neg A$". Below is a formal deduction showing that contradiction elimination and double negation elimination together give the ability to do proofs by contradiction:

[Suppose from "$\neg A$" you can derive "Contradiction".]

  If $\neg A$:

    Contradiction.

  Therefore $\neg \neg A$. [contradiction elimination / negation introduction]

  Thus $A$. [double negation elimination]

A contradiction isn't a “problem”. A contradiction is an impossibility. This isn't a matter of saying “Gee, if I have fewer than 20 dollars in the back I won't be able to go out to dinner and I want to so badly, I'll just assume I have more than 20 dollars.” This is a matter of walking into the bank and saying "I'd like to withdraw 20 dollars" and having a trapdoor under you collapse and a 300 lb security guard jumping on your spleen shouting in you ear “You don't have it!!! You don't have it!!”

You can't just say “Oh, I got a contradiction when I assumed I had 20 dollars... But that doesn't mean I don't have 20 dollars.”

It means precisely that. It is impossible for you to have 20. So you must conclude you don't have 20 dollars.

If you get a contradiction, it just isn't possible for A to be false.

A contradiction, by its definition is an impossibility. So if you assume A isn't true and you get a contradiction. You have proven that it is impossible for A not to be true. If it is impossible for something not to be true what other options are there?