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; the volatile part is versioned by buildnumber, so each deployment is side-by-side with the previous one. The drain/switchover is a manual process for now as we have a user acceptance step in the middle.
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.
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.