We could use a bloom filter for this! all messages that have some sort of reply (backlink, dig, reply) would be stored in a bloomfilter, which could be checked instantly.