This is what Bloom filters would solve. I believe another poster said that Firefox uses them to quickly check valid certs.