Cookies could be compliant with that, if they contained the entire session state and weren't a key into the session state on the server. They probably shouldn'

Cookies could be compliant with that, if they contained the entire session state and weren't a key into the session state on the server. They probably shouldn't be used like that, but technically it would be compliant with the requirements you've quoted.