For this sort of use-case v4 might be better. It has more randomness and you will probably delete the old ids as soon as they are used anyway, so the indexed space will probably be small.

How small is small, and how often is that state checked?

I guess it's probably not tracking tons of IDs like tracking packet state through a network device.

Even a few million (max) UUIDv4 is probably fine then, yeah?

Yeah, I'd say that sounds fine. Since these are supposed to be used within a short time it'd also be easy to cleanup unused ones more then 5mins old or so.