So wait, why does the refresh token not work? Why wouldn't you verify user permissions when generating a new access token?
Store CreationDate in the refresh token. Store RefreshTokenInvalidBefore in the user record. When refresh is attempted, if Token.CreationDate <= User.RefreshTokenInvalidBefore, reject the refresh. The only drawback here is that it would sign the user out on all devices. However, assuming this is because of a password or token compromise, that's likely the least of their worries.
And since the IDs in the revoked-tokens table only matter for the duration of token validity, you can prune the table pretty often, meaning necessary space needed in the DB is relatively small.
It's certainly more complicated than just dealing with stateful session tokens, so you might decide that the trade off isn't worth it, though.