The other catch with that approach is that requests can be simultaneous, fail, and/or arrive out-of-order, so the server would need to accept any authentication

The other catch with that approach is that requests can be simultaneous, fail, and/or arrive out-of-order, so the server would need to accept any authentication cookie that it had recently sent to the client, not just the last one. Not impossible, but not easy.