The point of using a stateless token is that you don't have to hit a central server / service to verify each token. If you need to do that in order to check for revoked tokens (for each request) then that defeats the purpose. At that point you may as well just check the original token / key for validity.

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?