It seems that the meaning of “statelessness” (hypothetically) goes beyond its practical expression.
Consider a web system without a database. You call the (RESTful) API, you always get exactly the same results. It is completely stateless ... But this is also not a real system.
A real system in almost every implementation contains data. Moreover, this data is the “resources” that the RESTful API allows us to access. Of course, data changes are also caused by API calls. So, if you get the value of a resource, change its value and then get its value again, you will get a different value than the first read; however, this clearly does not mean that the readings themselves were not stateless. They do not have citizenship in the sense that they represent the same action (or, more precisely, a resource) for each call. To change the value of a resource, you must perform it manually using another RESTful API, which will then be reflected in the next call.
However, what happens if we have a resource that changes without a manual standard API verb? For example, suppose we have a resource that counts the number of calls to another resource. Or some other resource that is populated with some other data from third parties. Obviously, this is still a protocol without preservation.
Moreover, in a sense, almost any system, say, any system that includes an authentication mechanism, responds differently to the same API calls, depending, for example, on user privileges. And yet, it is obvious that RESTful systems do not prohibit the authentication of their users ...
In short, stateless systems are void for this protocol. If Google tracks calls, so if I call the same resource in the same session, I get different answers, then it aborts the stateless requirement. But while the response returned is different due to application-level data and is not associated with the session, this requirement is not violated.
AFAIK, what Google does is not necessarily related to sessions. If the same user starts the same search under completely identical conditions (for example, IP, geographic location, OS, browser, etc.), they will receive the same answer. If a new identical search leads to different results due to what Google “recognized” in the last call, it is still stateless, because - again - this second call will produce the same result if it was done in another session but under the same conditions.