The difference in speed between checking for a token in the big pool (all tokens) vs the small pool (revoked tokens) should be a lot smaller than the round trip to token server (i.e. network cost).
Also, you should be able to easily store millions of tokens on a single server (something like Redis). Do you really have a site that has multiple millions of people logged in?
Depending on your situation, managing a revocation list in memory at each edge node might be feasible, reducing the overhead of a network call to a per-cluster store, which is another advantage of using a short revocation list instead of a large session store that can't feasibly be shared like that.
(Edit: looking back at my comment, I shouldn't have said a "shared" revocation list, but a distributed one. Whoops!)
Actually most people should take their authentication mechanism as something really really important and not just rely on something. It's really important that your authentication/authorization stuff works and is hardened, not just for you, also for your users. I know that auth could be really hard, especially when the language of your choice contains some bugs, but its a nogo to just use something when it is that important. I don't mean that you can't use a library, but if you do please double check the code twice on each version.
The approach I use is to replace the shared session store (which is large, grows linearly with your user base, and hard to sync across clusters if you need that) with a shared revocation list.
The revocation list is small, easy to check, only contains IDs and a TTL, much less cumbersome to replicate... And is functionally equivalent.
If you have already gone the route of using a token for your session, it's really easy to implement and scales much better than a massive in memory store.