The way I'd approach this is to treat "revocation" as meaning "after this user's current tokens expire, they can't refresh them," and make the token lifetime sh

The way I'd approach this is to treat "revocation" as meaning "after this user's current tokens expire, they can't refresh them," and make the token lifetime short enough that you're comfortable with it. Document that any API call can also include a "new_token": {...} field, and the client should update. On the server side, only try to refresh the token when it's close to expiring, and don't fail the API call if you can't reach the revocation server (just skip refreshing). You still have a central server to track account status, but now it can be more like "a text file with a list of usernames on a single box running Apache, if it crashes we reboot it" and less like "a distributed, high performance, highly-available in-memory K/V store that's in the critical path for every request," which is going to make you a lot happier operationally. Or you can push the list of usernames to revoke to each server, or something.