When is the Law of the Excluded Middle Valid/Not Valid? Sometimes, you can use the Law of the Excluded Middle (LEM) to validly prove things by contradiction (e.g. irrationality of sqrt(2)).
However, at other times, you can not, for example when you have self-referential statements (e.g. Liar Paradox).
My question is: Is there an algorithm/rule that allows one to decide when LEM can be validly used in a proof?
 A: In mainstream mathematics the law of excluded middle is always considered a valid proof step.
There are still some contexts where one is interested in the existence of proofs that avoid this law (as well as various other things deemed "non-constructive") but there's a firm expectation that one has to declare explicitly that one expects proofs in such a restricted style.
The mainstream response to the liar paradox is not to restrict the law of excluded middle, but to refuse completely to make self-referential statements as part of proofs.
Strictly speaking, what is forbidden is not self-reference, but any claims of the form "such-and-such is true" or "such-and-such is false" where "such-and-such" is not a concrete statement but instead an explanation of how to construct the statement we're talking about. This excludes both "this statement" and varieties such as "such-and-such preceded by a quotation of itself".
In practice we do allow writing things such as "Now, if equation (4) above is true, then bla bla bla", but only because the reader can easily unfold it to something where everything is explicit, as in "Now, if $x^2=e^{3x}-\sin^2\theta$, then bla bla bla".
Formulas that include "$\ldots$" are strictly speaking only recipes for making a statement, rather than statements themselves, and at such they are at risk of paradox unless we have a concrete definition that shows how to unfold them to something that does not refer to the truth of constructed statements -- often using an auxiliary recursive definition.

Mainstream mathematics can investigate self-referential statements by treating them as objects of study in an appropriately defined formal system -- running them "in a sandbox", as it were. They can be spoken about but not uttered as claims in their own right at the meta-level.
A: Your underlying question is philosophical, but that's fine; logic is just as much philosophy as it is mathematics. Let me state your question:

How do we know that LEM is always valid?

The only reasonable answer to this is that there is only one reality, and when we consider totally precise and unambiguous statements about this reality, it is necessarily the case that every such statement is either true or false about this reality, meaning that either it correctly describes reality, or it does not correctly describe reality. We don't care about statements that are ambiguous or not well-defined, just like we don't care about nonsense like ß\EÂ{8ÄäÉ5¨5;-c1÷ÌOm¶ÑzYè:ÏÁôví2QêIxú·9Ñ5u¤­åÉ¡nçßówâ§¸}tì-Ì«ÞB8r%sHÛæW¯*".vD because it is meaningless.
Based on this, we get classical logic. In classical logic one is only allowed to refer to objects that exist. Because of that, it is impossible to construct the liar sentence, because it is equivalent to:

??? Let $P$ be a sentence such that $P$ is equivalent to $\neg P$.

Which is clearly invalid because we have not proven that such a sentence exists. Indeed, we can show that no such sentence exists. Same for other paradoxes using self-reference (such as Curry's paradox) and paradoxes that assume the existence of objects without proof (such as the Barber paradox).
However, there is another deeper paradox in natural language. Consider the following sentence $S$:

" preceded by the quotation of itself is not a true sentence." preceded by the quotation of itself is not a true sentence.

Flawed argument: Notice that $S$ is a grammatically well-formed sentence of the form X is not a Y., so it ought to be true or false. If $S$ is a true sentence, then by what it claims, $S$ is not a true sentence. Therefore $S$ is not a true sentence. But then by what it claims, $S$ is a true sentence. Thus we get a contradiction.
Where is the error? Think for a while before continuing!
The key is that we will never be able to justify that $S$ is a statement about reality, and so we cannot apply LEM to it.
Sentences can be considered as strings of symbols in reality, so we can rightly say that $S$ is a sentence, and that "$S$ is a sentence" is a sentence, but once we want to say something about truth, it may not be a statement about reality anymore. Let us see what we can and cannot say regarding $S$. (Note that we always interpret "true sentence" to mean "true statement about reality" unless otherwise specified.)

First note that $S$ is the exactly the same string as " preceded by the quotation of itself is not a true sentence." preceded by the quotation of itself.
Thus $S$ is equivalent to asserting that $S$ is not a true sentence.   [(*)]
If $S$ is a true sentence:
  $S$.   [We can state $S$ since it is a true sentence.]
  $S$ is not a true sentence.   [By (*).]
  Contradiction.
If $S$ is not a true sentence:
  $S$.   [By (*).]
  $S$ is a true sentence.   [What we can validly state must be a true sentence.]
  Contradiction.
But we do not have LEM for "$S$ is a true sentence", since we did not prove that it is a statement about reality!
Thus all we can say is that "$S$ is a true sentence" is not a statement about reality, and likewise $S$ is not a statement about reality.

In general this approach can be used to resolve all paradoxes, including Quine's paradox (the one above) and Berry's paradox and the Surprise test paradox.
Note that some things like the circularity of modus ponens are not paradoxes but are intrinsically circular and cannot be justified non-circularly.
A: This answer relates to the following clarified question from the OP in comments:

But how can we prove a statement is not self-referential? And even if we can, how can we prove a given statement is not some other type of statement (like self-referential) that also doesn't work under LEM (a new type that would should ban too)? Sounds like all we can do is assume it works until shown that it doesn't, which doesn't sound very mathematical.

This question has a long history. It occurred to many other mathematicians, especially in the 19th century, when within 100 years they (1) learned of the independence of the parallel postulate in geometry, (2) learned of the ambiguity of the previous foundations of calculus and real analysis, and (3) learned of set-theoretic paradoxes such as Russell's paradox.
The quoted question really comes down to the consistency problem: how do we know that the systems we work with are consistent? Unfortunately, the generally accepted answer is that, to some extent, we do have to "assume" consistency. That may sound unfortunate at first, but it does not turn out to prevent us from doing math. I will explain a little more.
The natural idea was that, as a first step, we should make sure that the systems we work in are fully specified, unlike natural language. This led to the development of formal logical systems such as first-order logic, and formal foundational theories such as Peano Arithmetic (PA) and Zermelo-Fraenkel set theory (ZFC). These systems are unambiguously specified, so that the question of their consistency is a precise mathematical statement. (This is not the case with natural language, which is not fully specified.)
Now, we can ask: is it possible to prove that a system such as PA or ZFC is consistent? This is related to "Hilbert's program" pursued by David Hilbert and colleagues in the early 20th century.  There was a lot of progress on that question, including the famous "incompleteness theorems" of Kurt Gödel. 
There are many theorems related to the problem. For example, there are two independent proofs (by completely different methods) of the consistency of PA. But both of these proofs do require nontrivial axioms or deduction rules to carry out. If we wanted to prove the consistency of those axioms or deductive rules, we would need to assume some other axioms or deductive rules. In the end, you have to take some axioms for granted, or you have an infinite regress.  
Mathematicians differ on how to interpret this situation.  Some mathematicians view the consistency problem as solved, in that they either view PA and ZFC and being sufficiently "proved" consistent, or they view it as impossible to prove and thus not a mathematical question. Others think that the consistency of PA and ZFC is still an open problem which might be resolved in the future.  
This situation is not as bad as it may seem, however. Here is a common viewpoint among mathematical logicians today. 
First, we have been working with PA and ZFC for a long time, and despite many efforts, nobody has found a contradiction in them. So, heuristically, they seem to have stood up to the test of time. We don't have any proofs of their consistency with "no" assumptions, but we do have several proofs of their consistency "with" assumptions, and these proofs at least help us see what else would have to go wrong in order for these systems to be inconsistent. 
Second, if we did find a contradiction in a well known foundational system, it would be extremely interesting, because it would show us something we didn't know before. The most likely outcome is that we would modify the formal systems to avoid the new kind of paradox, and we would publish a lot of logic papers analyzing that paradox. 
Most logicians believe that discovering an inconsistency in our foundational systems would not "break" mathematics, because most ordinary mathematics can be done in many different formal systems, so we would still be able keep all or almost all of the results of ordinary mathematics, although we might formalize them differently.
Going back to LEM in particular, there is another result of Gödel relating to Peano arithmetic and its cousin without excluded middle, Heyting arithmetic.  Gödel showed that there is a completely effective procedure (an algorithm) that would take any formal proof of an inconsistency in Peano arithmetic and transform it into a formal proof an inconsistency in Heyting arithmetic. So, in the case of Peano arithmetic, if there is somehow an inconsistency, it isn't from LEM. This is just one of many, many theorems about the consistency problem. 
