You can implement sign out everywhere by setting a reauth flag on the user in the database. You lose the "completely stateless" aspect that JWT claims to provide, but it's a small trade-off for tighter security.
You are correct that the lookup doesn't have to be via the database. You could implement a caching system where the cache is invalidated when the user logs out and requires reauthentication. This is the notion of the session. By definition they cannot be stateless.
Stateless authentication is inherently (slightly) less secure than sessions. I think of a blind librarian who gives out keys to the library. Whoever has a key has access. You can put limitations on the timeframe someone has access to the library, but that's it. If your key gets stolen, the blind librarian can't help you as there is no way for him to tell if it's really you.
(This isn't a perfect scheme since a compromised issuer could have been induced to send post-dated tokens. If your need for global logout was to invalidate tokens issued by a compromised issuer, you'll need to blacklist keys as well)