CiviRules - What does 'Compare with original value (before the change)' do?
This comparison is pre-change. For example if I changed my surname from Smith to Jones and setup a condition to check surname = 'Smith' then setting this checkbox (Compare Original) would match to 'Smith' as that was my surname prior to the change I made. Hope that makes sense!
In terms of your use case - I think you've solved it the right way i.e. having a marker to indicate you've processed the contact already.