You are not throwing out a lot of babies with the bathwater if you would do it in a case of a known attack. You would invalidate ALL tokens of a user, which is a sane default especially since usually you wouldn't be able to rule out what other tokens were compromised. And yes, if it later turned out ALL your users and all their token were possibly compromised because you had some kind of security flaw, setting a global minimum_issued_at is exactly what you would do after you fixed the flaw. And yes, that means all your users must reauthenticate.
