And many providers don't. (Even big ones that are supposedly competent like Cloudflare.)
And basically everyone who uses granular API keys are storing a cleartext key, which is no better and possibly worse than storing a credential for an ACME account.
CAs can cache the record lookup for no longer than 10 days. After 10 days, they have to check it again. If the record is gone, which would be expected if the domain has expired or been transferred, then the authorization is no longer valid.
(I would have preferred a much shorter limit, like 8 hours, but 10 days is a lot better than the current 398 day limit for the original ACME DNS validation method.)
CAs were already doing something like this (CNAME to a dns server controlled by the CA), so there was interest from everyone involved to standardize and decide on what the rules should be.
To revoke the record, delete it from DNS. Let’s Encrypt queries authoritative nameservers with caches capped at 1 minute. Authorizations that have succeeded will soon be capped at 7 hours, though that’s independent of this challenge.