I mean, you aren't wrong. But I am challenged to think of a service that doesn't store state somewhere.

And you ignore the other situation. Even a fully "stateless" service that literally just responds to things probably doesn't want an outage just to deploy a new version.

That's true. The way we solve it is by splitting our infrastructure deployments in two parts: a volatile part and a persistent part; it gives us more confidence when deploying the stateless part, but sadly it also means that the persistent deployments don't get as much exercise as the stateless part and are somewhat more prone to bitrot.