Like Email to Case (standard), Email to Case Premium uses the standard Salesforce Case Thread ID to match inbound emails to existing cases. The Case Thread ID (ex: ref:_00Dxxxxx._500yyyyyyy:ref) is a minified combination of the Salesforce Organization ID and the Case Record ID.

Email to Case Premium locates the Case Thread ID by retrieving the last instance of text matching the Thread ID format with a matching Organization ID from the inbound's emails Subject, Text Body, and HTML body. It will then query for cases matching those results. If a case is found matching the thread id in the subject then that case is selected. Otherwise, the newest case is selected.
Starting in version 3.75, unlike Email to Case (standard), all Case Thread IDs with an Organization ID not matching the current running Organization ID will be ignored.
 

Email to Case Premium locates the Case Thread ID by searching fields on the inbound email in the following order.

1. Subject
2. Text Body
3. HTML Body

Considerations:

• If multiple Case Thread IDs are present, only the last match in a given field is used.
• If a Case Thread ID is found in the subject, neither the text body or html body will be searched.

Email to Case Premium (E2CP) will scan the entire email and extract the last instance of a string bounded by ref: and :ref from email subject, text body, and html body.  Then E2CP will expand the thread id matches into case ids and search for cases with those ids.