Duplicate Detection Rules can use lookups
I recently configured a duplicate detection rule that used a lookup field as the match field. I surprised at first that duplicate detection did not appear to work when adding duplicated records. I had checked that the entiy was enabled for duplicate checking and published the rule.
However, after a while, I found that the duplicate detection rule did work. So even if the rule has a status of published (which means that all the matchcodes have been generated) there might be a delay before it works.