My question is basically: when is it fair to look for the problem in the quality of the developers

There isn't enough information in your post to answer that question. There's no way to know if they are failing because they are incompetent, or failing because they commit to doing more work than is reasonable.

If I'm an incredibly gifted developer, on a team of incredibly gifted developers, and we sign up to send a rocket to the moon in two sprints while starting from scratch, are we incompetent? Or, do we just suck at estimation?

The problem starts with bad estimates

Estimation is hard. Really hard. Humans suck at it, which is why Scrum has us break work down into blocks that shouldn't take more than a day or two, and to assemble small groups of those blocks that we're certain we can complete in a short period of time. The bigger the blocks, and the longer the period of time, the less accurate our estimations are.

The problem is compounded by bad retrospectives

What you're doing wrong, seemingly, is that you aren't taking advantage of retrospectives. You've gone 18 months without solving this problem, so either the team isn't noticing the problem, or are failing to address it in their retrospectives.

The solution isn't to place blame, it is to learn

The first step should be to stop looking for blame, and instead, start working to improve the team. Your team is probably not incompetent, just bad at estimation and planning. Force the team to finish a sprint, even if that means they pick a single story and finish a week early. If they can't do that, then either they are incompetent, or the stories are simply too complex. The answer to that question should be obvious.

Once they are able to finish the one story, they will know with reasonable certainty that they can do X amount of story points in a sprint. Simple math will help answer the question of whether they can do more stories or not.

Continuous improvement is the solution

Once they finish one story in a sprint, it is time to see if they can do two. Lather, rinse, repeat. When they start failing the sprint goals, you've found the limit to their estimation abilities. Go back to the number of story points from the previous story and stick to that for a while.

At all times, take the retrospectives seriously. If they didn't finish a sprint, figure out why and act on it. Did they have too many unknowns? Do they have the wrong mix of skills? How good were their estimates? If they estimated a story to be X points, did it require a relatively equal amount of work as priory stories worth X points? If not, use that to adjust the points of stories going forward.

My question is basically: when is it fair to look for the problem in the quality of the developers

There isn't enough information in your post to answer that question. There's no way to know if they are failing because they are incompetent, or failing because they commit to doing more work than is reasonable.

If I'm an incredibly gifted developer, on a team of incredibly gifted developers, and we fail to finish X stories in two sprints (or 36!), are we incompetent? Or, do we just suck at estimation? That depends on if the stories were "create a login screen" or "send a man safely to mars".

The problem starts with bad stories and/or bad estimates

Estimation is hard. Really hard. Humans suck at it, which is why Scrum has us break work down into blocks that shouldn't take more than a day or two, and to assemble small groups of those blocks that we're certain we can complete in a short period of time. The bigger the blocks, and the longer the period of time, the less accurate our estimations are.

What are your stores like? Are they well written, with good acceptance criteria? Are they each small enough to do in just a few days? Without well written stories (which is the fault of the whole development team, including the product owner), the team can't be expected to do good estimation.

The problem is compounded by bad retrospectives

What you're doing wrong, seemingly, is that you aren't taking advantage of retrospectives. You've gone 18 months without solving this problem, so either the team isn't noticing the problem, or are failing to address it in their retrospectives.

Does each retrospective end with at least one action item for the team to take, in order to do better on the next sprint. Does each retrospective include talking about the action items from the previous sprint to see if they were done and if they were effective?

The solution isn't to place blame, it is to learn

The first step should be to stop looking for blame, and instead, start working to improve the team. Your team is probably not incompetent, just bad at estimation and planning. Force the team to finish a sprint, even if that means they pick a single story and finish a week early. If they can't do that, then either they are incompetent, or the stories are simply too complex. The answer to that question should be obvious.

Once they are able to finish the one story, they will know with reasonable certainty that they can do X amount of story points in a sprint. Simple math will help answer the question of whether they can do more stories or not.

Continuous improvement is the solution

Once they finish one story in a sprint, it is time to see if they can do two. Lather, rinse, repeat. When they start failing the sprint goals, you've found the limit to their estimation abilities. Go back to the number of story points from the previous story and stick to that for a while.

At all times, take the retrospectives seriously. If they didn't finish a sprint, figure out why and act on it. Did they have too many unknowns? Do they have the wrong mix of skills? How good were their estimates? If they estimated a story to be X points, did it require a relatively equal amount of work as priory stories worth X points? If not, use that to adjust the points of stories going forward.