My solution is to create a new custom field on the Case record of type "Formula (Text)". The field's value is the formula mentioned in the blog post:
TRIM(" [ ref:" + LEFT( $Organization.Id, 4) + RIGHT($Organization.Id, 4) +"."+ LEFT( Id, 4) + SUBSTITUTE(SUBSTITUTE(SUBSTITUTE(Id, RIGHT( Id, 4), ""), LEFT( Id, 4), ""), "0", "") + RIGHT( Id, 4) + ":ref ] ")
Now the value of the custom field for each Case record is the same as the reference Id in emails and I can simply query for it with the Salesforce API.