I worked this out by hand and I'd recommend you do the same. The paper defining the behavior of PEGs is here:
https://bford.info/pub/lang/peg.pdf . Section 3.3 is the relevant one, defining all the parsing rules.
As for the simple explanation of what's going wrong:
1. We try to parse `aaaaa` as if it opened with the pattern `a STR a`. [And, with foresight, let's observe that this is true of the way we want the parse to go.]
2. We match the `a` at the beginning of the input and try to parse `aaaa` as if it opened with the pattern `STR a`.
3. This repeats; we make the same guess that we're dealing with a recursive STR, we match an `a`, and then we try to parse `aaa` as if it opened with `STR a`. I didn't mention this before, but the first step of doing this is to match the first element of the concatenation, `STR`, against the input.
4. Here's where things go wrong. We still guess that we're dealing with a recursive STR, because that rule has priority over the terminal rule `STR = a`. With foresight, let's observe that in the parse we want, this guess will fail, because we need the third STR to be a literal `a`. In that world, we'd then match the two following `a`s and our parse would succeed.
5. However, when we try to match our recursive rule `a STR a` against our input `aaa`, this succeeds, because that's a correct match. We have an outer recursive STR and an inner terminal STR, yielding `aaa`.
6. Since our first guess that the suffix `__aaa`` opens with a recursive STR succeeded, we will never experiment with what would happen if it opened with a terminal STR, the way we wish it would.
7. That was our only chance; the whole parse will now fail to match in predictable ways.
-----
> The ordered choice operator should try all choices, not stop earlier.
You can't defend PEGs by saying you wish they were defined differently. That's not a defense!
Look at the paper:
> Alternation (case 1): If (e₁, xy) => (n₁, x) then (e₁ / e₂, xy) => (n₁ + 1, x). Alternative e₁ is first tested, and if it succeeds, the expression e₁ / e₂ succeeds without testing e₂.
It's hard to be clearer than that.