Comment by strken

You could use a Bloom filter, and just gaslight your users when a false positive happens.