Graham,
Something has to be different than you described. I just did a quick test BSV copy/pasting your rule into a test bsv & it worked fine.
When creating the second instance of Contacts with a dup email address, AwareIM properly turned Contacts.Duplicate to 'Yes' for the newly added intance. Of course the first one would not have been marked with a Yes until you run the FIND and UPDATE.
Your rule would not detect and fix removing the Yes once a duplicate is resolved.
This rule solved that:
IF EXISTS Contacts WHERE (Contacts.EmailAddress = ThisContacts.EmailAddress AND Contacts.ID <> ThisContacts.ID) Then
Contacts.Duplicate = 'Yes' ELSE Contacts.Duplicate='No'
Note that in the bold area I also removed an unnecessary THIS.
Tom