Assuming this needs to be optimized for massive scale, just hash the values to a single indexed field.
And use something other than an RDBMS. Put the hash in Redis and expire the key; your code simply does an existence check for the hash. You could probably handle gmail with a big enough cluster.
That super-normalized schema looks terrible.