[dexterdog]

You only have to validate the token. It doesn't have to be a database-type medium because you're not writing very often in fact all you're really doing is making sure the token is not invalid. The session data could be changing on every request which would be at least one write on every request. With this system you are only writing to the central medium on a session creation or a session invalidation.

[bigonlogn]

This is not entirely true. Since we talking about implementing stateful sessions, you could receive a valid token (stolen, out otherwise) after the user has logged out.

You are correct that the lookup doesn't have to be via the database. You could implement a caching system where the cache is invalidated when the user logs out and requires reauthentication. This is the notion of the session. By definition they cannot be stateless.

Stateless authentication is inherently (slightly) less secure than sessions. I think of a blind librarian who gives out keys to the library. Whoever has a key has access. You can put limitations on the timeframe someone has access to the library, but that's it. If your key gets stolen, the blind librarian can't help you as there is no way for him to tell if it's really you.