Yeah, of course you can do these things. I really meant to say, "there now exists server-side state for this" — I'm bothered by how existence of that state defeats the statelessness benefits of signature-based schemes, not the fact that I have to query a remote database.

Oh, and also: "only store a blacklist" does not work if you want to provide the "revoke this app you gave access to a while ago and now it's spamming" functionality like in most social networks.