TL;DR
You say that some teams believe the following:
[E]very story must be complete by the end of the sprint.
It may be true that some teams believe this common misconception, but it's factually incorrect. The Scrum framework requires that the Scrum Team must do its best to deliver a coherent Sprint Goal each Sprint. User stories (or, more canonically, Product Backlog Items) are means to an end, rather than an end unto themselves.
Focus on the Sprint Goal
Always remember that the goal of a Sprint isn't to complete lots of backlog items. The goal of a Sprint is to deliver the Sprint Goal.
The Scrum Guide explicitly says (emphasis and italics mine):
The selected Product Backlog items deliver one coherent function, which can be the Sprint Goal. The Sprint Goal can be any other coherence that causes the Development Team to work together rather than on separate initiatives.
So, having lots of user stories that are each treated as independent initiatives that all must be completed by the end of the Sprint in order for the Sprint to succeed is an anti-pattern. It's also explicitly verboten per the Scrum Guide. It's certainly common to see this pattern in shops struggling with agile adoption, but just because it's common doesn't make it agile (and it certainly isn't Scrum).
The question is whether the team can still meet the Sprint Goal if certain stories are not started, or will remain incomplete at the end of the Sprint. The only way to find out is to ask the Scrum Team, and then track progress toward the Sprint Goal in your burn-down chart, Kanban board, Sprint Backlog, or other artifacts. The Product Owner has the ability to renegotiate scope for the Sprint, or to cancel the Sprint and return to Sprint Planning, whenever the current Sprint Goal is at risk.
Sprint Goals and Increments
The following elements of the Scrum framework are explicitly defined in The Scrum Guide. The Sprint Goal is developed during Sprint Planning, and provides guidance throughout the Sprint. The Increment is the work completed according to the Definition of Done, and is essentially the de facto deliverable for the Sprint.
Sprint Goal
The selected Product Backlog items deliver one coherent function, which can be the Sprint Goal. The Sprint Goal can be any other coherence that causes the Development Team to work together rather than on separate initiatives.
Increment
At the end of a Sprint, the new Increment must be “Done,” which means it must be in useable condition and meet the Scrum Team’s definition of “Done.” It must be in useable condition regardless of whether the Product Owner decides to actually release it.
Sprint Failure Conditions
While not addressed specifically within The Scrum Guide, in practice a Sprint really has only three failure conditions:
- The Sprint Goal has not been met.
- The delivered Increment is not in usable condition.
- The Increment does not meet the "Definition of Done."
That's it. Individual stories can be done or not-done, forecasts (estimates) can be missed, and the team may have successfully delivered the wrong MacGuffin. Such Sprints are still technically "successful" in that they delivered a potentially-releasable Increment and leveraged the framework to provide the business with process transparency and appropriate opportunities to inspect-and-adapt.