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)
It's effectively a micro-optimization that will have no real effect, but you can do a simple "exists" query when searching the revocation list, and the TTL keeps the collection small.
Not advocating for JWT as it's a silly mess to do everything correctly, but it is possible.
Server-side key invalidation is entirely possible but it would require having a blacklist of disabled keys and comparing every requests against the black list. This would obviously concede the benefits of scale from JWT tokens since you are doing the same thing as server side sessions. However, the black list should be considered only as an escape hatch and need not be enabled at all times. In fact, once all the tokens in the black list expire, the black list itself can be disabled and things go back to the way they were.