In the latest Salesforce release (Winter ‘16) there was an update that changes how the Email Reference Id (aka Thread_Id) is generated.

Old Email Reference Id

The old email reference Id was in the format of [ ref:orgId.caseId:ref ] and was really easy to generate. All you had to do was concatenate the currentUser’s orgId and their caseId together

public static String refId (String orgId, String caseId) {
    return '[ ref:' + orgId + '.' + caseId + ':ref ]';
}

Run this and you’re done. Easy peasy.

New Email Reference Id

This all changed with the release of Winter ‘16. Once this hit the way the email reference Id changed so much that the Email to Case process wouldn’t even parse the old thread ids. So when a reply back to an email containing the old email reference id would come in, it would create a new case instead of pairing the EmailMessage with the Case Id in the thread_id.