Agreed they have to authenticate but I don't think they perform a lookup on every single request. They probably use a key but it is more likely this key (let's call it the AJAX key) is generated from the user's dat (id, ip, whatever else) using some hashing function on the back-end. When the server receives a request it can check to see if a request is valid by re-generating the AJAX key from the requests meta data (header or whatever other data sent with the request for authentication purposes). This is much quicker and more scalable than a lookup for every request and its just as secure. Even if someone guesses your key generation method (which should be HIGHLY unlikely) you can simply change it and it will work for all users immediately, even ones who are logged in already.
Now maybe they are performing a lookup for each request but I just do not see how they can handle the load, or why they would want to given the alternative I just suggested. Google sends a ridiculous amount of data back to their servers during a Gmail session. I haven't examined the traffic extensively but open up a chat box in gmail and the Firebug console at the same time. Click anywhere in the chat box. See the request that fires off int he console? That happens EACH TIME you click ANYWHERE in the box. I guess they are doing some type of clicking heat map or something I don't know, but whatever they are doing it requires sending potentially 1+ AJAX requests per second for many users.
I am not knowledgeable enough to tell you how much is too much for a server/file system/database to handle quickly (~150 ms per request for millions of requests at once) so maybe the situation I just described is not as bad as I made it seem.