Reduce[] giving incorrect result for equation over $\mathbb{Z}^4$

This is partially in response to a question I posted earlier, although the problem in this case appears to be distinct from the problem there, so I am temporarily filing this as a separate question.

Executing

Length[Reduce[Abs[c1] + Abs[c2] + Abs[c3] + Abs[c4] <= 19, {c1, c2, c3, c4}, Integers]]


yields 97281, which is in full agreement with the result obtained when Reduce is replaced by Solve.

However, executing

Length[Reduce[Abs[c1] + Abs[c2] + Abs[c3] + Abs[c4] <= 22, {c1, c2, c3, c4}, Integers]]


yields 42736. This is obviously impossible, since the number of $\mathbb{Z}^4$ lattice points within a taxicab ball is a strictly increasing function of radius.

Does anyone know what is going wrong here? I am going to temporarily solve the problem via alternate, more delicate approaches seeing as both Solve[] and Reduce[] have failed to give correct answers for $r\geq20$, but any insight as to this sudden behavioral discontinuity would be appreciated.

EDIT: It may be possible that the lower than expected result from Length may be due to Reduce outputting a solution set whose expression depth was not just that of the simple Or[...] structure that it normally gives for smaller values of $r$. If anyone can confirm this, I'll close this question.

-
I upvoted your last question. But this time, I really think it's your job to find out for certain whether the output actually is incorrect, rather than that it just has an unexpected structure. – Oleksandr R. Dec 25 '13 at 2:23
At the very least, it contains this (call the result sols and then run this): Cases[sols, Except@HoldPattern@And[__Equal], {1}]. Is this right or wrong? I'm not sure. As this is also the last element, I think Reduce is just telling us that it gave up exhaustively enumerating solutions at that point. – Oleksandr R. Dec 25 '13 at 2:32
@OleksandrR.: Artes recently told me about the option "ReduceOptions" -> "ExhaustiveSearchMaxPoints", which I'll try fiddling with once I'm finished with dinner. – DumpsterDoofus Dec 25 '13 at 2:36

If you try:

ListLinePlot[{#, Length@Reduce[Abs[c1] + Abs[c2] + Abs[c3] + Abs[c4] <= # &&
And @@ Thread[{c1, c2, c3, c4} >= 0], {c1, c2, c3, c4}, Integers]} & /@
Range[2, 20]]


You'll get:

It only means that Reduce[] is expressing its results in a different way. Take a look at them and then post your own answer :)

-
Thanks, I looked at them and it's clear that it's decided to stop using exhaustive enumeration. – DumpsterDoofus Dec 25 '13 at 4:01