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.