I did a bit more research on the use of "on all fours" in legal writing, and my research questions whether Michael Quinion is right when he suggests that the phrase refers to two animals standing next to each other (and thus similiarly situated). When I looked up the earliest uses of the phrase in American decisions, it turned out that they all refer to motion — the cases are running on all fours, or traveling on all fours, or going on all fours.

  Here are the four earliest uses of the phrase in state cases, all in contexts designed to mean "closely analogous":

Snelgrove v. Snelgrove, 4 S.C.Eq. 274, S.C., Jun 1812
"[Another precedent] is that most perfectly like the one now before the court. Indeed it may be said to run on all fours."

Gailey v. Beard, 4 Yeates 546, Pa., 1808
"The case in 2 Stra. 934, runs on all-fours with the present"

Abbott v. Broome, 2 Am.Dec. 187, N.Y.Sup., 1803
"The determination also in Saidler and Craig v. Church, goes on all fours with the present case. The facts were exactly similar."

Hamilton v. Buckwalter, 2 Yeates 389, Pa., 1798
"It is similar to the present case, and may be said to run on all-fours."

  And here are the earliest uses in federal decisions:

Russell v. Wiggin, 21 F.Cas. 68, C.C.D.Mass., May Term 1842
"[A prior precedent] is also an authority to the same purpose; and, indeed, it runs on all fours with the present case."

Bank of the U S v. Goddard, 2 F.Cas. 694, C.C.D.Mass., Oct Term 1829
"The case would seem, therefore, to travel on all-fours with the present."

The William Penn, 6 F.Cas. 781, C.C.D.N.J., Oct Term 1819
"[I]t would have been directly in point, and would have gone on all fours with the present."

Anonymous, 1 F.Cas. 1004, D.Md., 1808
"If this determination does not exactly run on all fours with the case to be decided, its principles are so nearly similar as to render an accurate discrimination very difficult."

  Later cases begin to drop the notion of "running" and just say that the former case "is" on all fours with the latter. This is just speculation, of course, but the context suggests that the visual image is more an animal running alongside the observer than two animals standing next to each other. If an animal is running on all four legs beside you, the thinking might be, it means that it remains close to you and goes where you go. So if a precedent runs on all fours with your case, it exactly tracks your case. That's my amateurish guess, at least.