It's intentional behavior. Pattern matching in some cases uses recursion. There is a brake in place to avoid kernel crashes from subroutine stack exhaustion. A brief history can be found here.

I'll track it down later. Morning coffee and a ten year old iPad...

I should be glad this bit of hardware isn't a defiant teenager.

Later edit: I think the link should work now. No idea how that previous one got copied to clipboard. The iPad keeps its secrets.

Eric,

I do not remember those details at all well. Indeed, I have to remind myself how things work any and every time I need to work with pattern matching code (I suppose that holds for pretty much all code I look at).

The rough idea is this. Certain pattern types, such as Blank(Null)Sequence and Repeated(Null), can match things of varying length. These tend to be "hard" cases, and will go into code that relies on recursion to try different possible partial matches. When these patterns are nested this can go into deep recursion.

Some other pattern types can similarly cause trouble. One is Alternatives, since the different possibilities can have vary different partial match features. So again there can be deep recursion.

I realize this is on the vague side of nebulous. It's not that I do not care to share more detail, so much as I do not want to drag myself back into that code. At least not until the next (mis-)assigned bug report takes me there.

From my Email conversation with Wolfram Support I learned now that your posts here where the official Wolfram development statements concerning my CASE:4955075.

Well, if so, I miss one statement: Considers Wolfram this behavior as a bug being repaired sometimes? Or do we have to live with it?

Thanks Daniel

OK, Daniel. I can live with it. It needs just omitting the default for the other parameters.

I reported the issue to Wolfram Support.

Weird. No answers, but some observations:

(1) This form works, but assumes that your matrix is rectangular:

fb[stuff_, base_Integer : 10] := {base, Length@stuff} /; MatrixQ[stuff, IntegerQ]

You didn't explicitly say that it should be rectangular, but your example is. I assume you can replace the condition with a more accurate one for your context. This also "works" without the condition, but then you're losing your constraints on the first argument.

(2) This also "works", but doesn't use your default:

fb[stuff : {{__Integer} ..}, base_Integer] := {base, Length@stuff}

So, it seems very much related to the default value.

(3) It doesn't help to use Default explicitly:

Default[fb] = 10;
fb[stuff : {{___} ...}, base_.] := {base, Length@stuff}

It works for small arguments, and breaks at 4999.

(4) Default values work without the extra pattern stuff:

Default[fb, 1] = {};
Default[fb, 2] = 10;
fb[stuff_., base_.] := {base, Length@stuff}

But again, you lose your other constraints.

(*) My conclusion is that this seems like a bug. But it's fascinating that there is some interaction across the argument patterns. It's also interesting that it breaks at 4999. I don't see how that's related to the recursion limit.