Has anyone explored using a technique like a Bloom filter or partial hash matching (like haveibeenpwned does) as a preliminary step for CRL lookups? You could do a cheap initial query, and if you get a negative, you're good. You only have to do the full expensive one if you get a positive, to ensure that it's a true positive. Which should be rare since most certs that are presented won't be revoked.