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 searching fields on the inbound email in the following order.
All Case Thread IDs with an Organization ID not matching the current running Organization ID will be ignored.
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.
Starting in Winter '21, Salesforce has removed the standard Case Thread Id field. Users of Email to Case Premium can continue to successfully utilize the packaged Thread Id field. More information on this change can be found here.