I used to teach some of the vocabulary of case law in English: the hierarchy of the courts; the importance of the ratio decidendi (roughly speaking, the logic behind a decision, rather than the specific facts); the difference between Rechtskraft (res judicata: a particular decision is final and unappealable) and stare decisis (new decisions should follow older ones by certain courts if they are on similar fact situations), overruling and a decision on appeal; binding and persuasive precedents; obiter dicta; distinguishing, and the declaratory theory of the common law (the law does not change, it is merely described more precisely). If a case is not on all fours with a suggested precedent, the court will distinguish, which does not mean ‘see a difference’ but ‘find a difference’ (The court distinguished the present case from Carruthers v. Witherspoon).

While I was away, first the Volokh Conspiracy (here and here) and then Mark Liberman of Language Log wrote on the origin and meaning of the term on all fours.

I first met the term in The English Legal System by Walker & Walker (don’t be put off by the amazon.co.uk review):

Cases which are indistinguishable are described as being “on all fours” with one another.

I had never encountered the earlier version to run on all fours, but the OED and other references give it. I am most convinced by the Liberman argument that one situation is on all fours with another if the comparison does not limp (der Vergleich hinkt nicht). I did think that it meant that the various points all tallied, but that may be wrong. It probably has nothing to do with the idea of a multi-legged decision.

Good German introduction to this topic in Dieter Blumenwitz, Einführung in das anglo-amerikanische Recht.
(Link removed re malware, 2017)

I see Black’s Law Dictionary links to a ‘slang’ synonym, whitehorse case, also known as horse case, goose case, or gray mule case:

A reported case with facts virtually identical to those of the instant case, so that the disposition of the reported case should determine the outcome of the present case.

This doesn’t Google too well and may be purely Texan (Garner is from Texas, I believe).