I guess it depends on how fast revoked sessions need to stop working and how many you have.

If eventual consistency is good enough, presumably you could use something that looks like a bloom filter of revoked tokens and only check ones that match against the revocation service, right?